On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and thre e machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive sc heduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competiti ve algorithm for the preemptive scheduling problem of three machines, which is most competitive. (C) 2001 Elsevier Science B.V. All rights reserved.