Competitive Algorithms for the Online Minimum Peak Job Scheduling

Célia Escribe (), Michael Hu () and Retsef Levi ()
Additional contact information
Célia Escribe: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Michael Hu: Health System Engineering, Massachusetts General Hospital, Boston, Massachusetts 02114
Retsef Levi: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2025, vol. 73, issue 1, 408-423

Abstract: This paper describes a fundamental online scheduling problem called the minimum peak job scheduling (MPJS) problem. In this problem, there is a sequence of arriving jobs, each with a specified required scheduled time for one unit of a scarce and reusable resource. The goal is to schedule each job upon arrival within a scheduling interval to minimize the resulting peak utilization (i.e., the maximum number of units used simultaneously throughout the entire scheduling interval). The MPJS problem captures many practical settings of real-time appointment scheduling. Its offline version where all jobs are known in advance is equivalent to the well-known bin-packing problem, where jobs correspond to items and the unit resource is a bin. However, the online variant of MPJS allows additional flexibility in that initially, one only commits to the scheduling time, but the allocation to the resources can be done later. In the bin-packing problem, this corresponds to the ability to move items across bins. Some relaxed versions of online bin-packing problems have already been studied, but none fundamentally capture the MPJS model studied in this paper. The paper describes the first competitive online algorithm to the MPJS problem called the harmonic rematching (HR) algorithm. The analysis shows that the HR algorithm has an asymptotic competitive ratio below 1.5. The fact that the current best lower bound on randomized online algorithms for the bin-packing problem is 1.536 highlights the fundamental difference between these two related models.

Keywords: Optimization; bin packing; online algorithm; competitive analysis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0080 (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:73:y:2025:i:1:p:408-423

Access Statistics for this article

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