# A heuristic for the two-machine open-shop scheduling problem with transportation times

Tools

Strusevich, V.A.
(1999)
*A heuristic for the two-machine open-shop scheduling
problem with transportation times.*
Discrete Applied Mathematics, 93 (2-3).
pp. 287-304.
ISSN 0166-218X
(doi:10.1016/S0166-218X(99)00115-8)

Official URL: http://dx.doi.org/10.1016/S0166-218X(99)00115-8

## Abstract

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimize the makespan, provided that preemption is not allowed and the interstage transportation times are involved. This problem is known to be unary NP-hard. We present an algorithm that requires O (n log n) time and provides a worst-case performance ratio of 3/2.

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

Uncontrolled Keywords: | open shop, transportation time, approximation, worst-case analysis |

Subjects: | Q Science > QA Mathematics > QA76 Computer software T Technology > T Technology (General) |

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

### Actions (login required)

View Item |