Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ejor.2009.09.023 | European Journal of Operational Research |
Keywords | DocType | Volume |
On-line scheduling,Open shops,Time lags,Greedy algorithm,Worst case analysis | Journal | 204 |
Issue | ISSN | Citations |
1 | 0377-2217 | 2 |
PageRank | References | Authors |
0.40 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiandong Zhang | 1 | 8 | 2.27 |
| Steef van de Velde | 2 | 21 | 3.31 |