Permutation flow shop scheduling: variability of completion time differences – NP-completeness. (8th May 2020) - König, Barbara; Leisten, Rainer; Stückrath, Jan
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.