Title: Permutation flow shop scheduling: variability of completion time differences – NP-completeness
Authors: Barbara König; Rainer Leisten; Jan Stückrath
Addresses: Faculty of Engineering, University of Duisburg-Essen, 47048 Duisburg, Germany ' Deceased; formerly of: University of Duisburg-Essen, 47048 Duisburg, Germany ' Faculty of Engineering, University of Duisburg-Essen, 47048 Duisburg, Germany
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.
Keywords: flow shop scheduling; variability of completion time differences; NP-completeness; optimisation; operational research.
International Journal of Operational Research, 2020 Vol.39 No.4, pp.562 - 573
Received: 10 Jul 2017
Accepted: 13 Mar 2018
Published online: 23 Nov 2020 *