Nikhil Bansal, Ning Chen, et al.
ACM Transactions on Algorithms
Paper
A (2 + ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
Abstract
In this paper we consider a generalized version of the classical preemptive open shop problem with sum of weighted job completion times objective. The main result is a (2 + ε)-approximation algorithm for this problem. In the last section we also discuss the possibility of improving our algorithm. © 2002 Elsevier Science (USA). All rights reserved.
Related
Conference paper
Improved approximation algorithms for broadcast scheduling
Nikhil Bansal, Don Coppersmith, et al.
SODA 2006
Nikhil Bansal, Don Coppersmiths, et al.
SIAM Journal on Computing
Conference paper
Test machine scheduling and optimization for z/OS
Matthew Kaplan, Tracy Kimbrel, et al.
CI-Sched 2007