Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6894537 | European Journal of Operational Research | 2018 | 28 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Matthias Bultmann, Sigrid Knust, Stefan Waldherr,