《2016 Single machine scheduling with release dates》.pdf

SIAM J. D c ISCRETE MATH. 2002 Society for Industrial and Applied Mathematics Vol. 15, No. 2, pp. 165–192 SINGLE MACHINE SCHEDULING WITH RELEASE DATES∗ MICHEL X. GOEMANS† , MAURICE QUEYRANNE‡ , ANDREAS S. SCHULZ§ , MARTIN SKUTELLA¶, AND YAOGUANG WANG Abstract. We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We firs tstudy two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion- time formulation. We show their equivalence by proving tha ta O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concep twhich enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concep tof common and independen α-points, respectively. The analysis implies in particular tha he worst-case relative error of the LP relaxations is a tmos t1.6853, and we provide instances showing tha ti tis a tleas e/(e − 1) ≈ 1.5819. Both algorithms may be derandomized; their deterministic versions run in O(n2 ) time. The randomized algorithms also apply to the on-line se ing, in which jobs arrive dynamically over time and one mus tdecide which job to process withou tknowledge of jobs tha twill be released afterwards. Key words. approximation algorithm, LP relaxa