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. As far as delay algorithms are concerned, no algorithm can do better than the greedy algorithm for the non-clairvoyant variant of the problem. For the clairvoyant variant, no on-line delay algorithm has a competitive ratio better than V2.

greedy algorithm, on-line scheduling, open shops, time lags, worst case analysis
dx.doi.org/10.1016/j.ejor.2009.09.023, hdl.handle.net/1765/21728
ERIM Top-Core Articles
European Journal of Operational Research
Erasmus Research Institute of Management

Zhang, X, & van de Velde, S.L. (2010). On-line two-machine open shop scheduling with time lags. European Journal of Operational Research, 204(1), 14–19. doi:10.1016/j.ejor.2009.09.023