Online Job Admission

In: S. S. Ravi and S. K. Shukla ed., Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz. Springer, 2007

Authors

• Stephan Westphal
• Sven O. Krumke
• Rob van Stee

Abstract

We consider the problem of scheduling a maximum profit selection of jobs on m identical machines. Jobs arrive online one by one and each job is specified by its start and end time. The goal is to determine a non-preemptive schedule which maximizes the profit of the scheduled jobs, where the profit of a job is equal to its length. Upon arrival of a new job, an online algorithm must decide whether to accept the job or not. If the job is accepted, the online algorithm must be able to reorganize its already existing schedule such that the new job can be processed together with all previously admitted jobs. The algorithm need not specify on which machine the job will eventually be run. We provide lower bounds on the competitive ratio for randomized algorithms against an oblivious adversary and present deterministic algorithms which essentially match the lower bounds.

BibTeX

 
@Article{ Krumke+etal:job-admission, 
   title = { Online Job Admission }, 
   author = { Stephan Westphal and Sven O. Krumke and Rob van Stee },  
   editor = { S. S. Ravi and S. K. Shukla }, 
   booktitle = { Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz },        
   publisher = { Springer },      
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.