# Scheduling batches with sequential job processing for two-machine flow and open shops

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:10.1287/ijoc.13.2.120.10521)

## 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: | |

Last Modified: | 14 Oct 2016 09:01 |

URI: | http://gala.gre.ac.uk/id/eprint/578 |

### Actions (login required)

View Item |