On permutation schedules for two-machine flow shops with buffer constraints and constant processing times on one machine

Philine Geser, Hoang Thanh Le, Tom Hartmann and Martin Middendorf

European Journal of Operational Research, 2022, vol. 303, issue 2, 593-601

Abstract: The two-machine flow shop problem with buffers where one of the machines has constant processing times is studied. It is investigated if optimal permutation schedules exist, i.e., schedules which minimize the makespan within the set of all schedules and where the job sequence on both machines is the same. Two standard buffer models (an intermediate buffer that a job occupies between its processing on the two machines and a spanning buffer which is occupied by a job over all of its processing steps) are considered for two types of buffer usage: i) all jobs occupy the same buffer amount and ii) for each job the occupied buffer amount equals its processing time on the machine with non-constant times. For (i) and both buffer models, it is shown that the set of optimal schedules always contains at least one permutation schedule. For (ii) the existence of optimal permutation schedules is only guaranteed for instances with n jobs for all n≤6 (spanning buffer) and for all n≤3 (intermediate buffer). For each n>6 (spanning buffer) and each n>3 (intermediate buffer) exists an instance which does not have an optimal permutation schedule. For (ii) and both buffer models, an upper bound and a lower bound for ratio between the makespan of a best permutation schedule and the makespan of an optimal schedule is given. It is also shown for (ii) and both buffer models that in general it is NP-hard to decide if an optimal permutation schedule exists.

Keywords: Scheduling; Constant Processing Times; Permutation Schedules, (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722002466
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:303:y:2022:i:2:p:593-601

DOI: 10.1016/j.ejor.2022.03.024

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