We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P_max/2 greater than the optimal schedule length, where P_max is the length of the longest job.
By: Eric J. Anderson, T. S. Jayram,Tracy Kimbrel
Published in: Computing , volume 67, (no 1), pages 83-90 in 2001
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 .