A Forward–Backward Relax-and-Solve Algorithm for the Resource-Constrained Project Scheduling Problem

Etminaniesfahani, A; Gu, H; Naeni, LM; Salehipour, A

A Forward–Backward Relax-and-Solve Algorithm for the Resource-Constrained Project Scheduling Problem

Etminaniesfahani, A Gu, H

Naeni, LM Salehipour, A

Permalink

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.

Adobe PDF

Download Accepted versionAdobe PDF (372.99 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Etminaniesfahani, A
dc.contributor.author	Gu, H https://orcid.org/0000-0003-2035-2583
dc.contributor.author	Naeni, LM
dc.contributor.author	Salehipour, A
dc.date.accessioned	2024-01-14T21:33:05Z
dc.date.available	2024-01-14T21:33:05Z
dc.date.issued	2023-03-01
dc.identifier.citation	SN Computer Science, 2023, 4, (2), pp. 104
dc.identifier.issn	2662-995X
dc.identifier.issn	2661-8907
dc.identifier.uri	http://hdl.handle.net/10453/174404
dc.description.abstract	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.
dc.language	en
dc.publisher	Springer Nature
dc.relation.ispartof	SN Computer Science
dc.relation.isbasedon	10.1007/s42979-022-01487-1
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org//10.1007/s42979-022-01487-1
dc.subject.classification	46 Information and computing sciences
dc.title	A Forward–Backward Relax-and-Solve Algorithm for the Resource-Constrained Project Scheduling Problem
dc.type	Journal Article
utslib.citation.volume	4
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building
pubs.organisational-group	/University of Technology Sydney/Faculty of Design, Architecture and Building/School of Built Environment
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access	*
dc.date.updated	2024-01-14T21:33:03Z
pubs.issue	2
pubs.publication-status	Published
pubs.volume	4
utslib.citation.issue	2

Abstract:

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:

http://hdl.handle.net/10453/174404