Online Job Scheduling on a Single Machine with General Cost Functions

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of online job scheduling on a single machine with general job-dependent cost functions. In this model, each job j has a processing requirement (length) vj and arrives with a nonnegative nondecreasing cost function gj(t), and this information is revealed to the system upon arrival of job j at time rj. The goal is to schedule the jobs preemptively on the machine in an online fashion so as to minimize the generalized completion time sumlimits{} {j{g_j}} left({{Cj}}right), where Cj is the completion time of job j on the machine. It is assumed that the machine has a unit processing speed that can work on a single job at any time instance. In particular, we are interested in finding an online scheduling policy whose objective cost is competitive with respect to a slower optimal offline benchmark, i.e., the one that knows all the job specifications a priori and is slower than the online algorithm. Under some mild assumptions, we provide a speed-augmented competitive algorithm for general nondecreasing cost functions gj(t) by utilizing a novel optimal control framework.

Original languageEnglish (US)
Title of host publication60th IEEE Conference on Decision and Control, CDC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665436595
StatePublished - 2021
Event60th IEEE Conference on Decision and Control, CDC 2021 - Austin, United States
Duration: Dec 13 2021Dec 17 2021

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Conference60th IEEE Conference on Decision and Control, CDC 2021
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Online Job Scheduling on a Single Machine with General Cost Functions'. Together they form a unique fingerprint.

Cite this