# Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

Drobouchevitch, I.G. and Strusevich, V.A.
(2000)
*Heuristics for the two-stage job shop scheduling problem with a bottleneck machine.*
European Journal of Operational Research, 123 (2).
pp. 229-240.
ISSN 0377-2217
(doi:10.1016/S0377-2217(99)00253-2)

## Abstract

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | job shop scheduling, approximation algorithm, worst-case analysis |

Subjects: | Q Science > QA Mathematics > QA76 Computer software T Technology > TS Manufactures |

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/391 |

### Actions (login required)

View Item |