Improved algorithms for proportionate flow shop scheduling with due-window assignment

Jin Qian () and Haiyan Han
Additional contact information
Jin Qian: Northeastern University
Haiyan Han: Northeastern University

Annals of Operations Research, 2022, vol. 309, issue 1, No 11, 249-258

Abstract: Abstract In a recent study, Sun et al. (AOR 292:113–131, 2020) studied due-window proportionate flow shop scheduling problems with position-dependent weights. For common due-window (denoted by CONW) and slack due-window (denoted by SLKW) assignment methods, they proved that these two problems can be solved in $$O(n^2\log n)$$ O ( n 2 log n ) time respectively, where n is the number of jobs. In this paper, we consider the same problems, and our contribution is that the CONW problem can be optimally solved by a lower-order algorithm, which runs in $$O(n\log n)$$ O ( n log n ) time, implying an improvement of a factor of n.

Keywords: Scheduling; Proportionate flow shop; Due-window assignment; Position-dependent weights; Algorithm complexity (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04414-4 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:309:y:2022:i:1:d:10.1007_s10479-021-04414-4

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

DOI: 10.1007/s10479-021-04414-4

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