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
1.47-Approximation algorithm for a preemptive single-machine scheduling problem
Abstract
In this note, we give a 1.47-approximation algorithm for the preemptive scheduling of jobs with release dates on a single machine so as to minimize the weighted sum of job completion times; this problem is denoted by 1|rj, pmtn|∑jwjCj in the notation of Lawler et al. Our result improves on a 2-approximation algorithm due to Hall et al. Math. Oper. Res. 22 (1997) 513-544, and also yields an improved bound on the quality of a well-known linear programming relaxation of the problem.