Name
Abstract | ||
|---|---|---|
This paper studies a flow shop where machines have some periods of limited availability. The limited availability may be due to preschedules, preventive maintenance, or overlap of two consecutive time horizons in the rolling time horizon planning algorithm. It is shown that the problem of minimizing makespan in such a flow shop is NP-hard in the strong sense, and that no polynomial time heuristic with constant relative error exists for the problem unless P=NP. Some important properties of optimal schedules are proved for two-machine flow shops. A branch and bound algorithm based on these properties is proposed, and results of computational experiments with the algorithm are presented. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0377-2217(01)00083-2 | European Journal of Operational Research |
Keywords | Field | DocType |
Scheduling theory,Flow shop systems,Non-availability periods,Schedule makespan | Heuristic,Mathematical optimization,Branch and bound,Time horizon,Job shop scheduling,Computer science,Flow shop scheduling,Schedule,Time complexity,Preventive maintenance,Operations management | Journal |
Volume | Issue | ISSN |
136 | 3 | 0377-2217 |
Citations | PageRank | References |
49 | 3.04 | 4 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wieslaw Kubiak | 1 | 540 | 62.61 |
| Jacek Blazewicz | 2 | 1064 | 154.23 |
| Piotr Formanowicz | 3 | 282 | 26.32 |
| Joachim Breit | 4 | 111 | 7.00 |
| Günter Schmidt | 5 | 87 | 9.93 |