Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints

Rodrigo A. Carrasco, Garud Iyengar, Cliff Stein

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In this work we combine resource augmentation and alpha-point scheduling techniques, which have resulted in very good performance scheduling algorithms, to compute approximate solutions for a general family of scheduling problems: each job has a convex non-decreasing cost function and the goal is to compute a schedule that minimizes the total cost subject to precedence constraints. We show that our algorithm is a O(1)-speed 1-approximation algorithm and our numerical experiments show that the speed-scaling ratio required is close to 1.

Original languageEnglish
Pages (from-to)436-441
Number of pages6
JournalOperations Research Letters
Volume41
Issue number5
DOIs
StatePublished - 2013

Keywords

  • Alpha-points
  • Approximation algorithms
  • Job-dependent convex cost
  • Scheduling
  • Speed scaling
  • Weighted tardiness

Fingerprint

Dive into the research topics of 'Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints'. Together they form a unique fingerprint.

Cite this