Competitive Algorithms for the Online Minimum Peak Job Scheduling

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.