Shakhlevich, Natalia V., Sotskov, Yuri N. and Werner, Frank (2000) Complexity of mixed shop scheduling problems: A survey. European Journal of Operational Research, 120. pp. 343-351. ISSN 0377-2217 (doi:10.1016/S0377-2217(99)00161-7)

Full text not available from this repository.

Abstract

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.

Item Type:	Article
Additional Information:	[1] Accepted: 1 October 1998. [2] Firstpblished online: 10 January 2000. [3] Published in print: 16 January 2000.
Uncontrolled Keywords:	optimal scheduling, mixture of job and open shops, polynomial algorithm, NP-hard problem
Subjects:	Q Science > QA Mathematics > QA76 Computer software T Technology > TJ Mechanical engineering and machinery
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:00
URI:	http://gala.gre.ac.uk/id/eprint/494

Actions (login required)

View Item