Glass, C.A., Potts, C.N. and Strusevich, V.A. (2001) Scheduling batches with sequential job processing for two-machine flow and open shops. INFORMS Journal on Computing, 13 (2). pp. 120-137. ISSN 1091-9856 (Print), 1526-5528 (Online) (doi:https://doi.org/10.1287/ijoc.13.2.120.10521)

Full text not available from this repository.

Abstract

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

Item Type:	Article
Uncontrolled Keywords:	production-scheduling, open-shop, flow-shop, analysis of algorithms, computational complexity, suboptimal algorithms
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
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 Publisher Organisation
Last Modified:	14 Oct 2016 09:01
URI:	http://gala.gre.ac.uk/id/eprint/578

Actions (login required)

View Item