Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems

Wei Wu, Takito Hayashi, Kato Haruyasu and Liang Tang

European Journal of Operational Research, 2023, vol. 307, issue 1, 82-102

Abstract: We study robust single-machine batch scheduling problems under uncertain processing times to minimize total flow time. Two types of batches are considered: serial batch (s-batch) and parallel batch (p-batch). These problems can model many on-site production and logistics applications which involve uncertain factors such as defect rates. We first prove that a sequencing rule for the shortest nominal processing time is optimal for both s-batch and p-batch problems. We then propose polynomial-time algorithms based on the observation that the robust batch scheduling problems are reducible or partially reducible to a constrained shortest path problem through worst-case scenario analysis. We further present more efficient algorithms for the special case of uniform maximum deviation times for all jobs. The algorithms are evaluated computationally, and the results show that their performance is satisfactory on the tested instances.

Keywords: Scheduling; Batch scheduling; Robust optimization; Shortest path problem; Polynomial-time algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722007615
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:307:y:2023:i:1:p:82-102

DOI: 10.1016/j.ejor.2022.09.032

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 ().