New heuristics for the RCPSP with multiple overlapping modes. (May 2019)

• Record Type: Journal Article
• Authors: Chu, Zihao; Xu, Zhe; Li, Haitao
• Is Part Of: Computers & industrial engineering. Volume 131(2019)
• Page Start: 146
• Page End: 156
• Publication Date: 2019-05
• Subjects: Resource-constrained project scheduling -- Concurrent engineering -- Multiple overlapping modes -- Approximate dynamic programming -- Rollout policy; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.03.044
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The rollout policy sequentially improves a base heuristic for the RCPSP-MOM. A pre-processing procedure further improves the quality of the basic rollout policy. Rollout heuristics outperform integer linear programming in solution quality. Rollout heuristics are efficient for medium and large instances. Abstract: Activity overlapping in project management and concurrent engineering allows a downstream activity to start before the end of its upstream activity based on some preliminary information and feedback. Because the preliminary information can be issued at multiple stages during an upstream activity's execution, the downstream activity may have multiple overlapping modes. Project scheduling with activity overlapping has a wide range of applications in manufacturing, R&D, construction and professional service industries. An optimal overlapping plan may help project manager accelerate project progress effectively with improved rate of investment. In this research, we study a resource-constrained project scheduling problem with multiple overlapping modes, which is NP-hard. To obtain high-quality near-optimal solutions, we formulate it as a dynamic program (DP), and develop a rollout policy based approximate dynamic programming (ADP) algorithm to obtain near-optimal policy efficiently. Our rollout policy sequentially improves over a priority-rule base policy. A rollout procedure based on pre-processing of overlapping options is also devised which we call pre-rollout. The pre-rollout improves over the rollout in some instances with moderately more computational time. A comprehensive experiment is performed on the PSPLIB benchmark instances. Computational results show that our rollout policy and the pre-rollout procedure significantly outperform the exact integer linear programming (ILP) solutions in both solution quality and computational time for medium and large instances.