A note on scheduling to meet two min-sum objectives |
| |
| Authors: | Eric Angel Aleksei V Fishkin |
| |
| Institution: | a LaMI, CNRS UMR 8042, Université d’Évry Val d’Essonne, France
b Department of Computer Science, University of Liverpool, Chadwick Building, Peach Street, Liverpool L69 7ZF, UK |
| |
| Abstract: | We consider a single machine scheduling problem with two min-sum objective functions: the sum of completion times and the sum of weighted completion times. We propose a simple polynomial time (1+(1/γ),1+γ)-approximation algorithm, and show that for γ>1, there is no (x,y)-approximation with 1<x<1+(1/γ) and 1<y<1+(γ-1)/(2+γ). |
| |
| Keywords: | Min-sum objectives Scheduling Completion time |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
