A note on scheduling to meet two min-sum objectives

A note on scheduling to meet two min-sum objectives

0.00 Avg rating—0 Votes
Article ID: iaor20072878
Country: Netherlands
Volume: 35
Issue: 1
Start Page Number: 69
End Page Number: 73
Publication Date: Jan 2007
Journal: Operations Research Letters
Authors: , ,
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+γ).

Reviews

Required fields are marked *. Your email address will not be published.