Parallel shifting bottleneck algorithms for non-permutation flow shop scheduling

Hossein Badri (), Tayebeh Bahreini () and Daniel Grosu ()
Additional contact information
Hossein Badri: Wayne State University
Tayebeh Bahreini: Wayne State University
Daniel Grosu: Wayne State University

Annals of Operations Research, 2024, vol. 343, issue 1, No 2, 39-65

Abstract: Abstract The flow shop scheduling problem is one of the most complex and widely applicable scheduling problem. In this paper, we design efficient parallel algorithms for solving large-size non-permutation flow shop scheduling problems by leveraging the huge amount of computing power of the current multi-core computing systems. We design two parallel algorithms based on the Shifting Bottleneck heuristic. The first one is a coarse-grained parallel algorithm that is suitable for execution on multi-core systems with a small number of cores, while the second one is a fine-grained parallel algorithm suitable for multi-core systems with a large number of cores. We perform an extensive experimental analysis to evaluate the performance of the proposed algorithms for instances of various sizes. The results show that the proposed algorithms can solve large-size instances of the problem in a reasonable amount of time and obtain solutions that are within acceptable distance from the lower bounds. The proposed parallel algorithms achieve good speedup with respect to the serial variants of the algorithms.

Keywords: Flow shop scheduling; Parallel algorithm; Shifting bottleneck heuristic (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06329-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:343:y:2024:i:1:d:10.1007_s10479-024-06329-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06329-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().