Permutation flow shop scheduling: variability of completion time differences – NP-completeness Online publication date: Mon, 23-Nov-2020
by Barbara König; Rainer Leisten; Jan Stückrath
International Journal of Operational Research (IJOR), Vol. 39, No. 4, 2020
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.
Online publication date: Mon, 23-Nov-2020
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Operational Research (IJOR):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email email@example.com