Strusevich, V.A. (2000) Group technology approach to the open shop scheduling problem with batch setup times. Operations Research Letters, 26 (4). pp. 181-192. ISSN 0167-6377 (doi:https://doi.org/10.1016/S0167-6377(00)00021-3)

Full text not available from this repository.

Abstract

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a -approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 5/4.

Item Type:	Article
Additional Information:	[1] Published online: 18 May 2000. [2] Published in print: May 2000.
Uncontrolled Keywords:	open shop, batching, group technology, approximation
Subjects:	Q Science > QA Mathematics > QA76 Computer software T Technology > TJ Mechanical engineering and machinery
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 09:00
URI:	http://gala.gre.ac.uk/id/eprint/393

Actions (login required)

View Item