Skip navigation

Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

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: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:
Last Modified: 14 Oct 2016 09:00
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/493

Actions (login required)

View Item View Item