Online and Offline Preemptive Two-Machine Job Shop Scheduling

        We Consider online and offline 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. Our results are:

      • A randomized online algorithm for the two-machine preemptive job shop that is 1.5-competitive against oblivious adversaries;
      • Lower bounds showing that the randomized bound of 1.5 and the trivial deterministic upper bound of 2 are asymptotically tight;
      • A linear-time 1.5-approximation algorithm for the two-machine preemptive job shop;
      • A polynomial time algorithm for the preemptive job shop with two jobs (and any number of machines);
      • A fully polynomial time approximation scheme (FPTAS) for preemptive and nonpreemptive job shops with a constant number of jobs (and any number of machines). Interestingly, the randomized algorithm requires only a single random bit.

By: Tracy Kimbrel, Jared Saia

Published in: Journal of Scheduling, volume 3, (no 6), pages 355-64 in 2000

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .