A tree search heuristic for the resource constrained project scheduling problem with transfer times

Ying Liu, Jing Zhou, Andrew Lim and Qian Hu

European Journal of Operational Research, 2023, vol. 304, issue 3, 939-951

Abstract: In this work, we study the resource constrained project scheduling problem with transfer times, where the transfer of resources between activities takes a certain amount of time. For the problem, we propose an improved serial schedule generation scheme, a new lower bound, and a tree search heuristic. To generate a schedule, the improved serial schedule generation scheme iteratively schedules an activity by breaking some existing resource flows and decides the earliest start time in an efficient way. The new lower bound is adapted from the critical capacity lower bound by additionally considering resource transfer times. The tree search heuristic utilizes the improved serial schedule generation scheme to schedule an activity at its earliest start time and the new lower bound to prune unpromising nodes in the search tree. Several priority rules are introduced in the heuristic for the selection of the next activity during branching and also used in a greedy algorithm to compute an upper bound for node evaluation. Computational experiments on benchmark instances show that the improved serial schedule generation scheme reduces the computational time by 91.30% on average compared to an existing serial schedule generation scheme from literature, the new lower bound dominates the known adapted critical path lower bound and achieves an average improvement of 7.95%, and the tree search heuristic performs better than three existing algorithms for the problem.

Keywords: Project scheduling; Transfer times; Schedule generation scheme; Tower bound; Tree search (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722003897
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:304:y:2023:i:3:p:939-951

DOI: 10.1016/j.ejor.2022.05.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().