Optimization models and a GA-based algorithm for stochastic time-cost trade-off problem

In real-life projects, both the trade-off between the project cost and the project completion time, and the uncertainty of the environment are considerable aspects for decision-makers. However, the research on the time-cost trade-off problem seldom concerns stochastic environments. Besides, optimizing the expected value of the objective is the exclusive decision-making criterion in the existing models for the stochastic time-cost trade-off problem. In this paper, two newly developed alternative stochastic time-cost trade-off models are proposed, in which the philosophies of chance-constrained programming and dependent-chance programming are adopted for decision-making. In addition, a hybrid intelligent algorithm integrating stochastic simulations and genetic algorithm is designed to search the quasi-optimal schedules under different decision-making criteria. The goal of the paper is to reveal how to obtain the optimal balance of the project completion time and the project cost in stochastic environments.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

Time-cost trade-off analysis of project networks in fuzzy environments

This paper proposes a novel approach for time-cost trade-off analysis of a project network in fuzzy environments. Different from the results of previous studies, in this paper the membership function of the fuzzy minimum total crash cost is constructed based on Zadeh’s extension principle and fuzzy solutions are provided. A pair of two-level mathematical programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy minimum total crash cost at α. By enumerating different values of α, the membership function of the fuzzy minimum total crash cost is constructed, and the corresponding optimal activity time for each activity is also obtained at the same time. An example of time-cost trade-off problem with several fuzzy parameters is solved successfully to demonstrate the validity of the proposed approach. Since the minimum total crash cost is expressed by a membership function rather than by a crisp value, the fuzziness of parameters is conserved completely, and more information is provided for time-cost trade-off analysis in project management. The proposed approach also can be applied to time-cost trade-off problems with other characteristics.     

Time-cost trade-off via optimal control theory in Markov PERT networks

We develop a new analytical model for the time-cost trade-off problem via optimal control theory in Markov PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. Then, we construct a multi-objective optimal control problem, in which the first objective is the minimization of the total direct costs of the project, in which the direct cost of each activity is a non-decreasing function of the resources allocated to it, the second objective is the minimization of the mean of project completion time and the third objective is the minimization of the variance of project completion time. Finally, two multi-objective decision techniques, viz, goal attainment and goal programming are applied to solve this multi-objective optimal control problem and obtain the optimal resources allocated to the activities or the control vector of the problem     

Experimental evaluation of simulated annealing algorithms for the time-cost trade-off problem

This paper evaluates variants of a simulated annealing algorithm which solve the total cost minimization problem in activity networks in the case that discrete time-cost execution modes are allowed on the project activities. This problem is a special case of the well known discrete time-cost trade-off problem (DTCTP). Based on a sample of randomly generated activity networks, formal tests of statistical significance are utilized to test both the quality of solutions and the time efficiency of algorithms versus problem factors. A procedure issued from the extreme values statistics is also applied on problem instances in order to determine, on the one hand, the confidence interval estimate of the optimum solution for each algorithm and, on the other hand, when to stop the running of an algorithm.     

On quadratic fractional generalized solid bi-criterion transportation problem

In this paper bi-criterion quadratic fractional generalized solid transportation problem is studied. An algorithm is devoloped to obtain the time-cost trade-off pairs and hence identifies the optimum trade-off pairs giving the equal priority to both time and cost. A numerical example is illustrated to support the algorithm.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

A Generalized Time–Cost Trade-Off Transportation Problem

In the classical transportation problem if the unit costs and transportation durations are considered, the time-cost trade-off solutions can be determined by the well-known threshold approach assuming that all the transportations are permitted to be simultaneous in time. If all the unit costs are linear functions of time over a specified interval of time, a parametric technique can be applied for identifying all the time-cost trade-off solutions pertaining to this interval. In this paper, the unit costs considered are piecewise linear non-increasing functions of time and transportations are allowed to be simultaneous. It is shown that a parametric method involving a finite sequence of parametric transportation problems reveals all the time-cost trade-off solutions of this generalized trade-off problem. Computational experience is included. If the transportation problem has considerable degeneracy, the parametric approach may pose some computational difficulty. This difficulty can be reduced by using an alternative method involving the bicriteria optimization approach of Aneja and Nair. Also, a direct method is outlined for the case where a finite set of discrete alternatives of unit cost-time pairs is available.     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。