Modeling and Solving the Deadline Satisfaction Problem in Line-of-Balance Scheduling

Abstract

This study investigates the deadline satisfaction problem in line-of-balance (LOB) scheduling, where each activity can be done concurrently in several units by hiring additional crews, and all employed crews are allocated to implement an activity in sequential units smoothly with no interruption. Furthermore, the project must be completed within a given deadline. In previous studies, the objective was to minimize the total number of crews under the assumption that the cost of hiring a crew is the same for all activities. In fact, this cost usually differs among activities because of the differences in type of work, crew size, and technical level of workers. This paper presents a mixed-integer linear programming model with an extended objective of minimizing the crew employment cost of all activities. The model is equipped with an exact procedure to validate the feasibility of a prespecified deadline. A highway project was used to show the application of the proposed method, and then extensive computational experiments were conducted to investigate the performance of the proposed method by comparing the obtained results with those obtained by the existing methods. The results highlight the significance of integrating the time-cost trade-off analysis, and indicate that the proposed method can find optimal solutions for large-scale projects within a reasonable amount of time.