On-line two-machine open shop scheduling with time lags |
| |
| Authors: | Xiandong Zhang Steef van de Velde |
| |
| Affiliation: | 1. Department of Management Science, School of Management, Fudan University, Shanghai 200433, China;2. Rotterdam School of Management, Erasmus University, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands |
| |
| Abstract: | We analyze the performance of the greedy algorithm for the on-line two-machine open shop scheduling problem of minimizing makespan, in which time lags exist between the completion time of the first and the start time of the second operation of any job. The competitive ratio for the greedy algorithm is 2, and it can be reduced to 5/3 if the maximum time lag is less than the minimum positive processing time of any operation. These ratios are tight. We also prove that no on-line non-delay algorithm can have a better competitive ratio. |
| |
| Keywords: | On-line scheduling Open shops Time lags Greedy algorithm Worst case analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
