Preemptive scheduling on two identical parallel machines with a single transporter |
| |
| Authors: | Hans Kellerer Alan J Soper Vitaly A Strusevich |
| |
| Institution: | 1. Institut für Statistik und Operations Research, Universit?t Graz, Universit?tsstra?e 15, 8010, Graz, Austria
2. School of Computing and Mathematical Sciences, Old Royal Naval College, University of Greenwich, Park Row, Greenwich, London, SE10 9LS, UK
|
| |
| Abstract: | We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed jobs are collected together on board the transporter. We identify the structural patterns of an optimal schedule and design an algorithm that either solves the problem to optimality or in the worst case behaves as a fully polynomial-time approximation scheme. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
