About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
On-line and off-line preemptive two-machine job shop scheduling
Abstract
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 offline case to yield a simple linear-time 1.5-approximation algorithm. Simple arguments yield lower bounds showing that the randomized online bound of 1.5 and the trivial deterministic on-line upper bound of 2 are asymptotically tight. Copyright © 2000 John Wiley & Sons, Ltd.
Related
Conference paper
End-to-end argumentation knowledge graph construction
Conference paper