Skip navigation

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

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

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)

Full text not available from this repository.

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
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/417

Actions (login required)

View Item View Item