مدل بهینه سازی MINLP برای مشکل تجارت کردن زمان-هزینه گسسته غیر خطی

This paper presents the mixed-integer nonlinear programming (MINLP) optimization model for the nonlinear discrete time–cost trade-off problem (NDTCTP). The nonlinear total project cost objective function of the proposed MINLP optimization model is subjected to a rigorous system of generalized precedence relationship constraints between project activities, project duration constraints, logical constraints, and a budget constraint. By means of the proposed MINLP optimization model, one can obtain the minimum total project cost, the project schedule with the optimal discrete start times and the optimal discrete durations of the activities, as well as the optimal time–cost curves of the project. The proposed model yields the exact optimum solution of the NDTCTP. Solving the NDTCTP, using the proposed MINLP model, avoids the need for (piece-wise) linear approximation of the nonlinear expressions. The MINLP model handles the discrete variables explicitly and requires no rounding of the continuous solution into an integer solution. The applicability of the proposed optimization model is not limited to weakly NDTCTPs. A numerical example from the literature and an example of the project time–cost trade-off analysis are presented at the end of the paper in order to show the advantages of the proposed model.

Cost effective project scheduling is an important issue in the planning process of a project. While the general scheduling of project activities is carried out before the submission of a tender, the executive project scheduling is performed before or during the realization of a project, Pšunder and Rebolj [1]. Execution of each project activity in normal duration requires employment of certain resources. Crashing an activity refers to the taking of additional resources at extra cost to reduce the duration of an activity below its normal value. The project time–cost trade-off optimization problem (TCTP) is concerned with crashing and scheduling a number of activities within a given project network in order to minimize the total cost of project execution. The TCTP is extensively discussed in project scheduling literature because of its practical relevance. Since the development of the critical path method (CPM) in the late 1950s, the TCTP has received substantial attention from numerous researchers and has generated a considerable number of publications covering the areas of optimization methods and optimization models. Various different optimization models have been proposed to solve the TCTP using either approximate heuristic methods or exact mathematical programming methods. Development of the optimization models for solving the TCTP using classical heuristic methods, such as genetic algorithms (GA) by Holland [2], simulated annealing (SA) by Kirkpatrick et al. [3], tabu search (TS) by Glover [4], neural networks (NNs) by Rumelhart et al. [5], ant colony optimization (ACO) by Dorigo et al. [6], and particle swarm optimization (PSO) by Kennedy and Eberhart [7], has been the subject of intensive research in project management. For instance, Feng et al. [8], Li et al. [9], Hegazy [10] and Leu and Yang [11] proposed the optimization models for solving the TCTP using the GA. Shtub et al. [12] and Azaron et al. [13] developed the SA model formulations. Gagnon et al. [14] proposed the TS optimization model to minimize the cost of the project. Adeli and Karim [15] have presented the NN model formulation for the cost optimal project scheduling. Xiong and Kuang [16] introduced an optimization model for solving the TCTP using the ACO algorithm. Recently, Yang [17] has proposed the PSO model formulation for the TCTP. The mathematical programming methods can be separated into linear programming (LP), Dantzig [18]; nonlinear programming (NLP), Karush [19] and Kuhn and Tucker [20]; mixed-integer linear programming (MILP), Land and Doig [21]; and mixed-integer nonlinear programming (MINLP), Benders [22]. While the LP and the NLP perform the optimization of continuous variables, the MILP and the MINLP execute a simultaneous optimization of continuous and discrete variables. Kelley [23] and Fulkerson [24] were the pioneers in formulating the TCTP as the LP model. However, even the earliest studies in this field recognized the nonlinear nature of the TCTP. Therefore, Kapur [25], Deckro et al. [26] and Klanšek and Pšunder [27] have developed the NLP models for solving the nonlinear TCTP. Since the nature of project scheduling problems is also discrete, meaning, that the project schedule is usually determined by the discrete time units (e.g. working day), the discrete optimization must be applied to handle the discrete variables explicitly. Meyer and Shaffer [28] proposed one of the first MILP optimization models, where they addressed the discrete time–cost relationships of the TCTP. A few years later, similar MILP optimization models for the TCTP were developed by Crowston and Thompson [29] and Crowston [30]. Thus, the MILP optimization models have been mainly applied to solve the discrete TCTP. The recent progress in this field may be found in contributions presented by Achuthan and Hardjawidjaja [31], Sakellaropoulos and Chassiakos [32], Vanhoucke [33], Akkan et al. [34]. Since the MILP can handle only linear relations between the variables, the nonlinear terms of the optimization model are usually approximated with linear or piece-wise linear functions. On the other hand, this paper presents the MINLP optimization model for solving the nonlinear discrete TCTP (NDTCTP). The nonlinear project cost objective function of the proposed MINLP optimization model is subjected to a rigorous system of generalized precedence relationship constraints between project activities, the project duration constraints, the logical constraints, and the budget constraint. By means of the proposed MINLP optimization model, one can obtain the minimum total project cost, the project schedule with the optimal discrete start times and the optimal discrete durations of the activities, as well as the optimal time–cost curves of the project. The proposed model yields the exact optimum solution of the NDTCTP. Solving the NDTCTP, using the proposed MINLP model, avoids the need for (piece-wise) linear approximation of the nonlinear expressions. The MINLP model handles the discrete variables explicitly and requires no rounding of the continuous solution into an integer solution. The applicability of the proposed optimization model is not limited to weakly NDTCTPs. A numerical example from the literature and an example of the project time–cost trade-off analysis are presented at the end of the paper in order to show the advantages of the proposed model.

This paper presents the mixed-integer nonlinear programming (MINLP) optimization model for the nonlinear discrete time–cost trade-off problem, NDTCTP. The MINLP-NDTCTP model formulation was developed and applied. The input data within the proposed MINLP-NDTCTP optimization model included: • the project network with determined preceding and succeeding activities; • the precedence relationships and the lag/lead times between the activities; • the project schedule superstructure with different alternatives for discrete start times and discrete durations of activities; • the target project duration; • the initial project cost and the daily project cost; • the per period penalty cost and the per period award bonus; • the total available project budget; • the direct cost-duration functions of the activities. The nonlinear total project cost objective function of the MINLP-NDTCTP model was subjected to a rigorous system of the generalized precedence relationship constraints between project activities, the project duration constraints, the logical constraints, and the budget constraint. In order to show the advantages of the proposed MINLP-NDTCTP optimization model, a numerical example from the literature and an example of the project time–cost trade-off analysis were presented in Section 4. The numerical example presented the exact discrete optimized project schedule using the MINLP-NDTCTP model. For specified input data, the proposed MINLP-NDTCTP optimization model yielded the minimum total project cost. The obtained optimal results were comprised of the project schedule with the optimal discrete start times and the optimal discrete durations of the activities. The MINLP optimization was carried out in a single and uniform calculating process, where the discrete start times and the discrete durations of project activities were considered simultaneously in order to obtain the minimum of the nonlinear total project cost. Thereupon, the paper also presented an example of the project time–cost trade-off analysis. The MINLP-NDTCTP model was applied and run repetitively for different combinations between actual and target project durations in order to obtain the optimum time–cost curves of the project. By means of the proposed MINLP-NDTCTP model and using presented repetitive procedure, one can develop the optimum time–cost curves of the project. This, in turn, may be used for evaluation of the optimal project duration that will lead to the minimum total project cost. The comparison between the optimum solution obtained using the MINLP-NDTCTP model and the optimum solution gained using the MILP model in [32] has demonstrated that both models are expected to find the exact optimum discrete solution for the NDTCTP. The MINLP-NDTCTP model is more complex and requires higher analytical/computational effort than the MILP model. On the other hand, the advantage of the MINLP-NDTCTP model with respect to the MILP model is in modeling capabilities. The proposed model uses nonlinear modeling since the time–cost function has a nonlinear shape. This would be the case if the time–cost function was continuous. However, for the specific practical problem, where each activity has a small number of discrete time–cost points, the MILP model can equally well find the optimum solution. The advantages and the drawbacks of the proposed MINLP-NDTCTP model with respect to the MILP model in [32] are summarized in Table 5.The MINLP-NDTCTP optimization model shows certain advantages over previous models. Namely, the proposed model yields the exact optimum solution of the NDTCTP, while the heuristic models calculate the approximate optimum solutions. Solving the NDTCTP, using the MINLP-NDTCTP model, avoids the need for (piece-wise) linear approximation of the nonlinear expressions, which has been the traditional approach proposed for solving this optimization problem, using the MILP models. Contrary to the NLP models, the MINLP-NDTCTP optimization model handles the discrete variables explicitly, requires no rounding of the continuous solution into an integer solution, and guarantees the optimality of the calculated discrete solution. Since the state-of-the-art MINLP methods can efficiently solve comprehensive and highly nonlinear MINLP problems, the applicability of the MINLP-NDTCTP optimization model is not limited to weakly NDTCTPs. In this way, the proposed MINLP-NDTCTP model is intended to be of considerable value to practitioners in project management.