An Optimal Control Framework for Online Job Scheduling with General Cost Functions

S. Rasoul Etesami ()
Additional contact information
S. Rasoul Etesami: Department of Industrial and Systems Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign, Urbana, Illinois 61801

Operations Research, 2022, vol. 70, issue 5, 2674-2701

Abstract: We consider the problem of online job scheduling on a single machine or multiple unrelated machines with general job and machine-dependent cost functions. In this model, each job has a processing requirement and arrives with a nonnegative nondecreasing cost function and this information is revealed to the system on arrival of that job. The goal is to dispatch the jobs to the machines in an online fashion and process them preemptively on the machines to minimize the generalized integral completion time. It is assumed that jobs cannot migrate between machines and that each machine has a fixed 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, that is, the one that knows all the job specifications a priori and is slower than the online algorithm. We first show that for the case of a single machine and special cost functions the highest-density-first rule is optimal for the generalized fractional completion time. We then extend this result by giving a speed-augmented competitive algorithm for the general nondecreasing cost functions by using a novel optimal control framework. This approach provides a principled method for identifying dual variables in different settings of online job scheduling with general cost functions. Using this method, we also provide a speed-augmented competitive algorithm for multiple unrelated machines with nondecreasing convex functions, where the competitive ratio depends on the curvature of the cost functions.

Keywords: Operations and Supply Chains; online job scheduling; generalized completion time; competitive ratio; speed augmentation; optimal control; network flow; linear programming duality (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2321 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2674-2701

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().