Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using Inclusion–Exclusion

Olivier Ploton () and Vincent T’kindt ()
Additional contact information
Olivier Ploton: Université de Tours
Vincent T’kindt: Université de Tours

Journal of Scheduling, 2023, vol. 26, issue 2, No 2, 137-145

Abstract: Abstract In this paper, we are interested in minimizing the maximal or total cost of jobs in a permutation flowshop. This problem is known to be strongly NP-hard and exact algorithms of practical interest to solve it have very high, often factorial, worst-case complexity bounds. From a more theoretical point of view, we describe an Inclusion–Exclusion-based exact algorithm with a moderate exponential time and a pseudopolynomial space worst-case complexity bound for a fixed number of machines. We discuss extensions of this algorithm for job precedence constraints, with moderate exponential space and time bounds.

Keywords: Scheduling; Worst-case complexity; Flowshop; Inclusion–Exclusion (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00759-1 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:jsched:v:26:y:2023:i:2:d:10.1007_s10951-022-00759-1

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

DOI: 10.1007/s10951-022-00759-1

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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