Shakhlevich, Natalia V., Sotskov, Yuri N. and Werner, Frank (1999) Shop-scheduling problems with fixed and non-fixed machine orders of the jobs. Annals of Operations Research, 92. pp. 281-304. ISSN 0254-5330 (Print), 1572-9338 (Online) (doi:https://doi.org/10.1023/A:1018943016617)

Full text not available from this repository.

Abstract

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, 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). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Item Type:	Article
Uncontrolled Keywords:	shop-scheduling, polynomial algorithm, NP-hard problem
Subjects:	Q Science > QA Mathematics
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/493

Actions (login required)

View Item