Synchronous flow shop scheduling with pliable jobs

Autor(en): Bultmann, Matthias 
Knust, Sigrid 
Waldherr, Stefan 
Stichwörter: ALGORITHMS; Business & Economics; Flow shop; MACHINES; MAKESPAN; Management; Operations Research & Management Science; Pliability; Scheduling; SEQUENCING PROBLEM; Synchronous movement
Erscheinungsdatum: 2018
Herausgeber: ELSEVIER SCIENCE BV
Journal: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volumen: 270
Ausgabe: 3
Startseite: 943
Seitenende: 956
Zusammenfassung: 
In this paper, we consider synchronous flow shop scheduling problems where the processing times of the operations are not fixed in advance. Instead, for each job a total processing time is given which can be distributed freely among the machines, respecting some lower and/or upper bounds on the processing times of the operations. We prove that even if no additional bounds are given, minimizing the makespan is NP-hard already for two machines. On the other hand, we can draw on a more general result to show that for a fixed job permutation optimal corresponding processing times can be determined via a linear program in polynomial time. However, for larger problem instances, this leads to large run times. As a more efficient alternative, we propose direct combinatorial algorithms to determine the processing times. We embed these algorithms in a two-stage approach using the set of all job permutations as search space and calculating corresponding processing times in a second step. Computational results are presented for randomly generated data with varying degrees of allowed flexibility. (C) 2018 Elsevier B.V. All rights reserved.
ISSN: 03772217
DOI: 10.1016/j.ejor.2018.04.024

Show full item record

Page view(s)

3
Last Week
0
Last month
0
checked on Feb 22, 2024

Google ScholarTM

Check

Altmetric