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.

DOI: 10.1504/IJOR.2020.111343

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article