We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 ). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 ), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.
- Dual fitting
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics