Flow shop scheduling with flexible processing times
Autor(en): | Bultmann, Matthias Knust, Sigrid Waldherr, Stefan |
Stichwörter: | Flexible processing times; Flow shop; JOBS; MACHINE; MAKESPAN; Operations Research & Management Science; Processing time redistribution; Scheduling; SEQUENCING PROBLEM | Erscheinungsdatum: | 2018 | Herausgeber: | SPRINGER | Journal: | OR SPECTRUM | Volumen: | 40 | Ausgabe: | 3 | Startseite: | 809 | Seitenende: | 829 | Zusammenfassung: | In numerous flow shop variants, the processing times of the operations are not fixed in advance, but may be distributed with some flexibility among the machines. In this paper, we introduce a general model which is expressive enough to cover several models from the literature. While in most cases it is -hard to find a job permutation and a corresponding distribution of processing times minimizing the makespan, we show that for a fixed job permutation a best processing time distribution can be calculated in polynomial time by linear programming. Based on this, we propose a tabu search procedure using the set of all job permutations as search space. In a computational study, we show the power of the new model. Besides the classical permutation flow shop environment, we study variants with blocking, no-wait and synchronous movement constraints. |
ISSN: | 01716468 | DOI: | 10.1007/s00291-018-0520-8 |
Show full item record