2019/04/12 by Chris Schwiegelshohn, Schwiegelshohn, Chris, Uwe Schwiegelshohn +1
Computer Science · Engineering · #68W27 #68W40 #Advanced Wireless Network Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1904.06150
openalex publication_date 2019/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate online scheduling with commitment for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. As soon as a job has been submitted, the commitment constraint forces us to decide immediately whether we accept or reject the job. Upon acceptance of a job, we must complete it before its deadline d that satisfies d ≥ (1+ε)⋅ p + r, with p and r being the processing time and the submission time of the job, respectively while ε>0 is the slack of the system. Since the hard case typically arises for near-tight deadlines, we consider ε≤ 1. We use competitive analysis to evaluate our algorithms. Our first main contribution is a deterministic preemptive online algorithm with an almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound \frac1+εε of the greedy acceptance policy. Then the competitive ratio improves with an increasing number of machines and approaches (1+ε)⋅ln \frac1+εε as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small ε. In the non-preemptive case, we present a deterministic algorithm on m machines with a competitive ratio of 1+m⋅ (\frac1+εε)(1)/(m). This matches the optimal bound of 2+\frac1ε of the greedy acceptance policy for a single machine while it again guarantees an exponential improvement over the greedy acceptance policy for small ε and large m. In addition, we determine an almost tight lower bound that approaches m⋅ (\frac1ε)(1)/(m) for large m and small ε.