New characteristics of optimal solutions for the two-machine flowshop problem with unlimited buffers

Ghaith Rabadi, Mohamed Kais Msakni, Elkin Rodriguez-Velasquez and William Alvarez-Bermudez

Journal of the Operational Research Society, 2019, vol. 70, issue 6, 962-973

Abstract: The two-machine flowshop problem with unlimited buffers with the objective of minimising the makespan (F2||Cmax) is addressed. Johnson’s algorithm finds optimal solutions (permutations) to this problem, but are not necessarily the only optimal solutions. We show in this paper that certain jobs that we define as Critical Jobs, must occupy specific positions in any optimal sequence, not only in Johnson’s solutions. We also prove that jobs that precede a critical job cannot be exchanged with jobs that succeed it in an optimal sequence, which reduces the number of enumerations necessary to identify all optimal solutions. The findings of this research can be useful in reducing the search space for optimal enumeration algorithms such as branch-and-bound.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2018.1475114 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:70:y:2019:i:6:p:962-973

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2018.1475114

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().