# Heuristics for short route job shop scheduling problems

Drobouchevitch, Inna G. and Strusevich, Vitaly A.
(1998)
*Heuristics for short route job shop scheduling problems.*
Mathematical Methods of Operations Research, 48 (3).
pp. 359-375.
ISSN 1432-2994 (Print), 1432-5217 (Online)
(doi:10.1007/s001860050033)

## Abstract

We consider two “minimum”NP-hard job shop scheduling problems to minimize the makespan. In one of the problems every job has to be processed on at most two out of three available machines. In the other problem there are two machines, and a job may visit one of the machines twice. For each problem, we define a class of heuristic schedules in which certain subsets of operations are kept as blocks on the corresponding machines. We show that for each problem the value of the makespan of the best schedule in that class cannot be less than 3/2 times the optimal value, and present algorithms that guarantee a worst-case ratio of 3/2.

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

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

Subjects: | Q Science > QA Mathematics |

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 08:59 |

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

### Actions (login required)

View Item |