Scheduling with Deadlines and Buffer Management with Processing Requirements

Scheduling with Deadlines and Buffer Management with Processing Requirements

0.00 Avg rating0 Votes
Article ID: iaor20173033
Volume: 78
Issue: 4
Start Page Number: 1246
End Page Number: 1262
Publication Date: Aug 2017
Journal: Algorithmica
Authors: ,
Keywords: combinatorial optimization, scheduling, production, queues: applications
Abstract:

We discuss the well known online job scheduling problem with release times and deadlines, alongside an extended model–buffer management for packets with processing requirements. For job scheduling, an Ω log κ log log κ equ1 lower bound on the competitive ratio of any randomized preemptive algorithm was shown by Canetti and Irani (Proceedings of the 27th annual ACM symposium on Theory of computing, ACM, pp 606–615, 1995), where κ equ2 is the the maximum job duration or the maximum job value (the minimum is assumed to be 1). The proof of this well‐known result is fairly elaborate and involved. In contrast, we show a significantly improved lower bound of Ω ( log κ ) equ3 using a simple proof. Our result matches the easy upper bound and closes a gap which was supposedly open for 20 years. We also discuss the problem of handling a FIFO buffer of a limited capacity, where packets arrive over time and may be preempted. Most of the work in buffer management considers the case where each packet has unit processing requirement. We consider a model where packets require some number of processing cycles before they can be transmitted. We aim to maximize the value of transmitted packets. We show an Ω log κ log log κ equ4 lower bound on the competitive ratio of randomized algorithms in this setting. We also present bounds for several special cases. For packets with unit values we also show a φ 1.618 equ5 lower bound on the competitive ratio of deterministic algorithms, and a 2‐competitive algorithm. For the case of packets with constant densities we present a 4‐competitive algorithm.

Reviews

Required fields are marked *. Your email address will not be published.