Time-cost Tradeoff Models For Scheduling Repetitive Projects And Their Extensions

Time-cost tradeoff problem has been the subject of extensive research in project scheduling; it aims to minimizing the total cost of the project without exceeding a given deadline. Repetitive projects involve a number of units of work to be finished and a set of activities that need to be repeated for each unit in the length of the job. Examples of such projects include high-rise building, highways, pipelines, and housing projects. The objective of this paper is to develop computable mathematical models for solving the time-cost tradeoff problem in repetitive projects (TCTPRP problem). Since the TCTPRP problem belongs to NP-hard problem, there is no known polynomial-time algorithm and even small problems may be hard to solve. Therefore, approximate models or heuristic algorithms will be further studied to handle large-size problems.Compared with non-repetitive projects, scheduling decision for repetitive projects become more complex because there is a need to determine the execution modes of activities, the numbers of crews should be employed for each activity, the logic sequences of different units, and the corresponding unit assignment strategy. Then, a perfect TCTPRP model in theory should have the ability to handle multiple crews, multiple modes, and non-fixed logic sequence (referred to as soft logic). In practice, however, not all repetitive projects have been allowed to employ multiple crews for activities, adjust the execution modes of activities, or change the logic sequence between units. Therefore, this paper studies the TCTPRP problem under different restrictions as the existing researches have done.The main study in this paper is detailed as follow:(1) This paper studies the multi-crew TCTPRP problem considering single mode and fixed logic with the objective to determine the optimal numbers of crews employed for activities and their start times in each unit.We adopts the approach of mixed integer linear programming to construct an exact model. Then, an approximate model, which owns the ability to deal with large-size problems in a short period of time, is developed by requiring all units in each activity to be performed with the same delivery. Extensive computational experiments demonstrate that the exact model can solve moderate-sized instances within the run-time of one hour up to 50 activities,100 units and 10 crews; the approximate model can solve the instances up to 100 activities and the average deviation is not more than 1%. After that, we extend the exact model to optimize non-typical projects in which activity duration may be vary from one unit to another. The extended model can determine the optimal unit assignment strategy for each activity.(2) This paper studies the multi-mode TCTPRP problem consider single crew and fixed logic with the objective to determine the optimal modes of activities and their start times in each unit.We presents an exact model taking the form of mixed integer linear programming, and two mode elimination rules that can effectively reduce the search size by removing those infeasible modes or feasible but not optimal modes. For large-size problems, we develop a two-phase heuristic procedure that are based on the linear programming relaxation idea. Our computational experiments show that within the run-time of one hour, the exact model can solve the instances up to 60 activities,40 units and 20 modes; the average deviation of the heuristic procedure is not more than 4%.(3) This paper studies the single-crew multi-mode soft logic TCTPRP problem with the objective to determine the optimal logic sequence between units, execution modes of activities and their start times in each unit.We analyze the possible effects of soft logic on repetitive project scheduling, and develop a mixed integer nonlinear programming model for problem description. Then, a heuristic algorithm that are based on genetic algorithm and linear programming idea is presented to solve the proposed model.The existing studies only considered the multi-crew TCTPRP problem with typical projects and multi-mode TCTPRP model with single crew and fixed logic, and their solution procedures were constructed by using intelligence algorithm in which the quality of solutions obtained was not properly addressed. Our work to some extent makes up for the shortcoming of the existing researches, and the computational results may be used as benchmarks to evaluate the performance of other heuristic methods.