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

This paper studies the problem of scheduling jobs in a two-machine open sho p 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 j ob in some batch to a job of another batch. For this NP-hard problem, we pr opose a linear-time heuristic algorithm that creates a group technology sch edule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a (5)/(4)-approximation algorithm. Moreover, we shaw that no group technology algorithm can guarantee a worst-case performance ratio les s than (5)/(4). (C) 2000 Elsevier Science B.V. All rights reserved.