Personal tools
 

An Online Scheduling Algorithm for Non-Preemptive, Equal-Length Jobs Using Two Identical Machines

— filed under:

Mark Pedigo, SLU

What
  • Computer Science Seminar
When Mon, Nov 21, 2005
from 03:10 PM to 04:00 PM
Where RH 202
Add event to calendar vCal
iCal

Abstract: We present an online algorithm which schedules non-preemptive, equal length jobs using two identical machines. Our goal is to maximize the number of jobs which can be scheduled by their deadlines. Each job has an arbitrary release date and deadline, which is revealed to the scheduler only upon its release time. We analyze this algorithm by comparing its results to an optimal offline schedule. In this way, we show that the algorithm is 3/2 competitive.

« December 2017 »
December
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31