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
Volumen: 40
Ausgabe: 3
Startseite: 809
Seitenende: 829
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

Page view(s)

Last Week
Last month
checked on Feb 22, 2024

Google ScholarTM