A Forward–Backward Relax-and-Solve Algorithm for the Resource-Constrained Project Scheduling Problem
- Publisher:
- Springer Nature
- Publication Type:
- Journal Article
- Citation:
- SN Computer Science, 2023, 4, (2), pp. 104
- Issue Date:
- 2023-03-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Scheduling projects under limited resource availability, which is called the resource-constrained project scheduling problem (RCPSP), has a wide range of real-world applications, e.g., in mining, manufacturing and supply chain. The RCPSP is NP-hard, and over the last five decades researchers attempted to propose various solution techniques for this challenging problem. The relax-and-solve (R&S) algorithm is a recently proposed method for solving various scheduling problems, such as job-shop and single and parallel machine scheduling problems. This research contributes to the existing research on the R&S by presenting an easy-to-implement and effective R&S method for solving RCPSP. Our R&S employs CPLEX CP optimizer as an optimization solver to generate and optimize schedules within a heuristic framework. We further improve the algorithm’s performance by employing forward–backward passes. The results of testing the algorithms on 1560 standard instances from the well-known PSPLIB show our heuristic delivers competitive results and outperforms state-of-the-art methods for solving the RCPSP.
Please use this identifier to cite or link to this item: