Online nonpreemptive scheduling of equal-length jobs on two identical machines

We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2008-11, Vol.5 (1), p.1-18
Main Authors: Goldwasser, Michael H., Pedigo, Mark
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.
ISSN:1549-6325
1549-6333
DOI:10.1145/1435375.1435377