Gupta, J.N.D., Strusevich, V.A. and Zwaneveld, C.M. (1997) Two-stage no-wait scheduling models with setup and removal times separated. Computers & Operations Research, 24 (11). pp. 1025-1031. ISSN 0305-0548 (doi:10.1016/S0305-0548(97)00018-X)

Full text not available from this repository.

Abstract

This paper studies two models of two-stage processing with no-wait in process. The first model is the two-machine flow shop, and the other is the assembly model. For both models we consider the problem of minimizing the makespan, provided that the setup and removal times are separated from the processing times. Each of these scheduling problems is reduced to the Traveling Salesman Problem (TSP). We show that, in general, the assembly problem is NP-hard in the strong sense. On the other hand, the two-machine flow shop problem reduces to the Gilmore-Gomory TSP, and is solvable in polynomial time. The same holds for the assembly problem under some reasonable assumptions. Using these and existing results, we provide a complete complexity classification of the relevant two-stage no-wait scheduling models.

Item Type:	Article
Uncontrolled Keywords:	two-stage no-wait scheduling models, setup time, removal time
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:	Publisher
Last Modified:	14 Oct 2016 08:59
URI:	http://gala.gre.ac.uk/id/eprint/57

Actions (login required)

View Item