Elsevier

Theoretical Computer Science

Volume 477, 18 March 2013, Pages 57-66
Theoretical Computer Science

Single machine scheduling with scenarios

https://doi.org/10.1016/j.tcs.2012.12.006Get rights and content
Under an Elsevier user license
open archive

Abstract

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective of minimizing the weighted sum of completion times. We model uncertainty by replacing the vector of numerical values in the description of the instance by a set of possible vectors, called scenarios. The goal is to find a schedule of minimum value in the worst-case scenario.

We first show that the general problem cannot be approximated within O(log1εn) for any ε>0, unless NP has quasi-polynomial algorithms. We then study more tractable special cases and obtain a linear program (LP)-based 2-approximation algorithm for the unweighted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6/5.

We conclude by presenting a polynomial-time algorithm based on dynamic programming for the case when the number of scenarios and the values of the instance are bounded by some constant.

Keywords

Robust optimization
Scheduling
Approximation algorithms
Inapproximability

Cited by (0)

A preliminary version of this article appeared in the proceedings of APPROX’08.