Tighter bounds on preemptive job shop scheduling with two machines
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/12 greater than the optimal schedule length, where P-max is the length of the longest job.
job shop scheduling approximation algorithm preemption