On-line and off-line preemptive two-machine job shop scheduling

We consider on-line and off-line algorithms for special cases of preemptive job shop scheduling to minimize makespan. These special cases are of interest because they commonly arise in the scheduling of computer systems. We give a randomized on-line algorithm for the two-machine preemptive job shop that is 1.5-competitive against oblivious adversaries. The algorithm assigns priority for one machine according to an arbitrary permutation of the jobs, and in the opposite order for the other machine. A single random bit is used to select which machine is assigned which of the two orders. Thus, our algorithm is easily derandomized in the off-line case to yield a simple linear-time 1.5-approximation algorithm. Simple arguments yield lower bounds showing that the randomized on-line bound of 1.5 and the trivial deterministic on-line upper bound of 2 are asymptotically tight.