Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Shop scheduling problems with pliable jobs

: Knust, S.; Shakhlevich, N.; Waldherr, S.; Weiß, C.


Journal of scheduling 22 (2019), Nr.6, S.635-661
ISSN: 1094-6136 (Print)
ISSN: 1099-1425 (Online)
Fraunhofer ITWM ()
scheduling; flow shop; Open Shop; identical parallel machine; preemption

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.