Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to es...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2000-01, Vol.120 (2), p.343-351
Main Authors: Shakhlevich, Natalia V., Sotskov, Yuri N., Werner, Frank
Format: Article
Language:English
Subjects:
[formula omitted]-hard problem
Algorithms
Job shops
Mixture of job and open shops
Operations research
Optimal scheduling
Polynomial algorithm
Production scheduling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, some jobs have fixed machine orders (as in the job shop), while the operations of the other jobs may be processed in arbitrary order (as in the open shop). The main attention is devoted to establishing the boundary between polynomially solvable and NP -hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(99)00161-7