مدل های بهینه سازی قوی برای مشکل تجارت کردن زمان / هزینه گسسته

Developing models and algorithms to generate robust project schedules that are less sensitive to disturbances are essential in today's highly competitive uncertain project environments. This paper addresses robust scheduling in project environments; specifically, we address the discrete time/cost trade-off problem (DTCTP). We formulate the robust DTCTP with three alternative optimization models in which interval uncertainty is assumed for the unknown cost parameters. We develop exact and heuristic algorithms to solve these robust optimization models. Furthermore, we compare the schedules that have been generated with these models on the basis of schedule robustness.

In project management it is often possible, with some additional costs, to reduce the duration of some activities and thereby expedite the project completion. In this paper, we consider discrete time/cost relationships and address the discrete time/cost trade-off problem (DTCTP), which is a well-known multi-mode project scheduling problem with practical relevance. Two main versions of the problem have been studied in the literature; namely, the deadline problem (DTCTP-D), the budget problem (DTCTP-B). In DTCTP-D, given a set of time/cost pairs (modes) and a project deadline of δ, each activity is assigned to one of the possible modes so that the total cost is minimized. The budget problem minimizes the project duration while meeting a given budget, B. We address the deadline version and formally define as Given a project with a set of n activities along with the corresponding precedence graph in the AoN (activity-on-node) representation, G =(N , A ), where N is the set of nodes, which includes n activities and two dummy nodes, 0 and n +1, that are used to indicate the project start and completion instants. A⊆N×NA⊆N×N is the set of arcs, which represents the immediate precedence constraints among activities. Each activity j can be performed at one of the |M j| modes where each mode m∈Mjm∈Mj, is characterized by a processing time pjmpjm and a cost cjmcjm. A mixed integer-programming model of the DTCTP-D can be stated as follows: equation(1.0) View the MathML sourceMin∑j=1n∑m∈Mjcjmxjm Turn MathJax on Subject to equation(1.1) View the MathML source∑m∈Mjxjm=1,j=1,…,n Turn MathJax on equation(1.2) View the MathML sourceCj−Ci−∑m∈Mjpjmxjm≥0∀(i,j)∈A Turn MathJax on equation(1.3) Cn+1≤δCn+1≤δ Turn MathJax on equation(1.4) View the MathML sourceCj≥0∀j∈N Turn MathJax on equation(1.5) View the MathML sourcexjm∈{0,1}∀m∈Mj,j=1,…,n Turn MathJax on C j is the continuous decision variable that represents the completion time of activity j . The binary decision variable x jm assigns a mode m∈Mjm∈Mj to activity j (1.5). Total cost is be minimized (1.0), while a unique mode should be assigned to each activity (1.1); precedence constraints should not be violated (1.2); and the deadline should be met (1.3). De et al. (1997) have shown that the DTCTP is strongly NP-hard. In their survey paper (1995), they review the problem characteristics, as well as exact and approximate solution strategies. Demeulemeester et al., 1996 and Demeulemeester et al., 1998 propose branch-and-bound to solve the problem exactly, Akkan et al. (2005), and Vanhoucke and Debels (2007) propose approximate algorithms. Additionally, Erenguc et al. (1993) use Benders decomposition to solve the DTCTP with discounted cash flows and Lova et al. (2009) propose a hybrid genetic algorithm to solve the resource constrained case. All of the studies cited above assume complete information and a deterministic environment; however, projects are often subject to various sources of uncertainty that threaten the accomplishment of project objectives. Therefore it is vital to develop effective robust scheduling algorithms. To minimize the effect of unexpected events on project performance, five fundamental scheduling approaches have been used: stochastic scheduling, fuzzy scheduling, sensitivity analysis, reactive scheduling, and robust (proactive) scheduling (Herroelen and Leus, 2005). In stochastic project scheduling, the activity durations are modeled as random variables and probability distributions are used. Fuzzy project scheduling uses fuzzy membership functions to model activity durations. The effects of parameter changes are investigated in sensitivity analysis. In reactive scheduling, the schedule is modified when a disruption occurs, whereas in robust scheduling anticipation of variability is incorporated into the schedule and schedules that are insensitive to disruptions are generated. Herroelen and Leus (2005) divide schedule robustness into two groups: solution robustness (stability) and quality robustness. The solution robustness is defined as the insensitivity of the activity start times with respect to variations in the input data. On the other hand, quality robustness is defined as insensitivity of schedule performance such as project makespan with respect to disruptions. Quality robust scheduling aims to construct schedules in such a way that the value of the performance measure is affected as little as possible by disruptions. In this research, we address on quality robust project scheduling. To construct solution robust project schedules, Herroelen and Leus (2003) propose some mathematical programming models. They develop an LP model and propose heuristics for the solution of robust scheduling. Their LP model allows a single activity disruption which increases the duration of one activity during the schedule execution. In addition, Van De Vonder et al. (2008) propose heuristics for solution robust scheduling and compare the performance of proposed heuristics using simulation. On the other hand, Lambrechts et al. (2008a) investigate the uncertainty in resource availabilities that may be caused by reasons such as machine failures, and they combine a proactive scheduling procedure with a reactive improvement procedure. Recently, Al-Fawzan and Haouari (2005), Chtourou and Haouari (2008), Kobylanski and Kuchta (2007), and Lambrechts et al. (2008b) have proposed predictive robustness measures for resource constrained networks. In a different vein from the studies cited above, we assume interval uncertainty and make use of robust optimization to generate robust project schedules. Robust optimization is a modeling approach to generate a plan that performs well even in the worst-case scenarios. Robust optimization has been applied to some combinatorial optimization problems such as the shortest path problem during the last decade ( Bertsimas and Sim, 2003). However, it has been implemented in only a few project scheduling problems as discussed below. Valls et al. (1998) examine a special resource constrained project scheduling problem (RCPSP) in which the activities might be interrupted for an uncertain period. Yamashita et al. (2007) address the resource availability cost problem (RACP). They propose two alternative models: the first model minimizes the maximum regret function, whereas the second one is a mean risk model that minimizes weighted sum of the mean and variance of the costs. Both Valls et al. (1998) and Yamashita et al. (2007) follow a scenario-based approach, where a scenario represents a realization of the duration of the activities. Alternatively, Cohen et al. (2007) use interval uncertainty in their recent robust scheduling study that addresses the effects of uncertainty on the continuous time-cost trade-off problem. They model the robust problem using the ARC methodology of Ben-Tal et al. (2004); some of the variables are determined before the realization of the uncertain parameters (non-adjustable variables), while the other variables could be determined after the realization (adjustable variables). We propose three robust optimization models in which uncertainty is modeled via intervals for the DTCTP-D. Our research differs from the previous studies in the literature regarding both the problem addressed and uncertainty modeling approach followed. Our models address the uncertainty in activity costs. In practice, fluctuations in the exchange rates, factor prices or resource usages result in cost variability. These fluctuations threaten the accomplishment of project cost objectives and it is essential to develop systematic methods to generate robust project schedules, which are less sensitive to uncertainty. We develop exact and heuristic algorithms to solve these robust models and compare the schedules that have been generated with these models on the basis of schedule robustness. The main contribution is the incorporation of uncertainty into a practically relevant project scheduling problem and the development of problem specific solution approaches. In the next section, we formulate the robust DTCTP-D using alternative robust optimization models. We propose exact and heuristic algorithms to solve these robust models in Section 3. Finally in Section 4, we present some computational results and compare the robustness of the schedules generated with these models using some robustness metrics.

In this paper, we have proposed three models to formulate the robust DTCTP. These models assume interval uncertainty for activity costs. It is assumed that the activity times are known with certainty when the mode of the activity is fixed and all the uncertainty is captured by the cost of the activity. In order to solve these models, we have developed both exact and approximate algorithms. The first model is solved exactly by using Benders decomposition; the other two criticality-based models are rather complex and solved approximately by a tabu search algorithm. The main advantage of Model 1 is that it could be solved exactly. However, the limitation is that the activities with the same cost intervals are assumed to be equally uncertain and all activities are likely to have cost values at the upper bounds. To evaluate the performance of the algorithms under various problem settings, we have conducted computational experiments. We have assessed the robustness of the schedules generated by the algorithms by using several cost based robustness measures. The models developed in this manuscript address the requirement to generate robust project schedules that are less sensitive to uncertainty. To the best of our knowledge, the models are the first implementation of robust optimization to the DTCTP. In that sense, results presented serve as a useful base to fill the research gap in developing robust project schedules for multi-mode project networks. In addition, they provide decision support to managers in project planning under uncertainty. As a future extension of this research, robust optimization models could be formulated for Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP), which allows the use of both renewable and nonrenewable resources. For this new generalized problem setting, in addition to the uncertainty costs, the uncertainty in activity durations or in resource requirements or in resource availabilities should also be addressed.