Permutation flow shop scheduling: variability of completion time differences – NP-completeness. (8th May 2020)

• Record Type: Journal Article
• Authors: König, Barbara; Leisten, Rainer; Stückrath, Jan
• Is Part Of: International journal of operational research. Volume 39:Number 4(2020)
• Page Start: 562
• Page End: 573
• Publication Date: 2020-05-08
• Subjects: flow shop scheduling -- variability of completion time differences -- NP-completeness -- optimisation -- operational research; Operations research -- Periodicals; 003.05
• Languages: English
• ISSNs: 1745-7645

Abstract

We consider the permutation flow shop scheduling problem and aim to obtain smoothness of jobs' completion times, by minimising the variance or the variability of inter-completion times. This problem, including an efficient heuristics, was introduced in Leisten and Rajendran (2015). Here we solve an open problem from that paper and show that the problem for more than two machines is NP-complete.