New characteristics of optimal solutions for the two-machine flowshop problem with unlimited buffers. Issue 6 (3rd June 2019)

• Record Type: Journal Article
• Authors: Rabadi, Ghaith; Msakni, Mohamed Kais; Rodriguez-Velasquez, Elkin; Alvarez-Bermudez, William
• Is Part Of: Journal of the Operational Research Society. Volume 70:Issue 6(2019)
• Page Start: 962
• Page End: 973
• Publication Date: 2019-06-03
• Subjects: Scheduling -- two-machine flowshop -- makespan -- critical job; Operations research -- Periodicals; 658.4034
• DOI: 10.1080/01605682.2018.1475114
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: The two-machine flowshop problem with unlimited buffers with the objective of minimising the makespan ( F 2|| C max ) 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.