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 |
Zur Langanzeige
Seitenaufrufe
4
Letzte Woche
0
0
Letzter Monat
1
1
geprüft am 01.06.2024