Flow shop scheduling with flexible processing times

Matthias Bultmann (), Sigrid Knust () and Stefan Waldherr ()
Additional contact information
Matthias Bultmann: University of Osnabrück
Sigrid Knust: University of Osnabrück
Stefan Waldherr: Technical University of Munich

OR Spectrum: Quantitative Approaches in Management, 2018, vol. 40, issue 3, No 8, 809-829

Abstract: Abstract 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 $$\mathcal {NP}$$ NP -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.

Keywords: Scheduling; Flow shop; Flexible processing times; Processing time redistribution (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-018-0520-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:40:y:2018:i:3:d:10.1007_s00291-018-0520-8

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-018-0520-8

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().