Abstract
In this paper, we study a new type of flow shop and open shop models, which handle so-called “pliable” jobs: their total processing times are given, but individual processing times of operations which make up these jobs are flexible and need to be determined. Our analysis demonstrates that many versions of flow shop and open shop problems with pliable jobs appear to be computationally easier than their traditional counterparts, unless the jobs have job-dependent restrictions imposed on minimum and maximum operation lengths. In the latter case, most problems with pliability become NP-hard even in the case of two machines.
| Original language | English |
|---|---|
| Pages (from-to) | 635-661 |
| Number of pages | 27 |
| Journal | Journal of Scheduling |
| Volume | 22 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - Dec 2019 |
| Externally published | Yes |
Funding
The authors thank the referee for suggestions aimed at improving the paper. This work was supported by the Deutsche Forschungsgemeinschaft, KN 512/7-1. The work of Stefan Waldherr was supported by the TUM Institute for Advanced Study through a Hans Fischer Senior Fellowship. The work of N.V.?Shakhlevich was supported by the EPSRC Grant EP/K041274/1.
| Funders | Funder number |
|---|---|
| Engineering and Physical Sciences Research Council | EP/K041274/1 |
| Deutsche Forschungsgemeinschaft | KN 512/7-1 |
| Institute for Advanced Study, Technische Universität München |
Keywords
- Flow shop
- Identical parallel machines
- Open shop
- Preemption
- Scheduling