Skip navigation

Group technology approach to the open shop scheduling problem with batch setup times

Group technology approach to the open shop scheduling problem with batch setup times

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:
Last Modified: 14 Oct 2016 09:00
URI: http://gala.gre.ac.uk/id/eprint/393

Actions (login required)

View Item View Item