Two-machine open shop scheduling with special transportation times
Rebaine, D. and Strusevich, V.A. (1999) Two-machine open shop scheduling with special transportation times. Journal of the Operational Research Society, 50. pp. 756-764. ISSN 0160-5682 (doi:https://doi.org/10.1057/palgrave.jors.2600769)
Full text not available from this repository.Abstract
The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | open shop scheduling, transportation time, two machines |
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/395 |
Actions (login required)
View Item |