Personal tools

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

— filed under:

Mark Pedigo, SLU

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

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.

« April 2018 »
Upcoming Events
Math/CS Club
Wed, Apr 25, 2018
The Mathematical Match Game Brody Johnson, SLU
PhD Oral Defense
Thu, Apr 26, 2018
Finite, fiber-preserving group actions on orientable Seifert manifolds Benjamin Peet, SLU
PhD Oral Exam
Fri, Apr 27, 2018
Leavitt Path Superalgebras Katie Radler, SLU
Annual Awards Ceremony
Fri, Apr 27, 2018
The 2018 Math & Statistics Department Award Ceremony Featuring Sarah Greenwald, Appalachian State University
Geometry/ Topology Seminar
Tue, May 01, 2018
Necessary and Sufficient Conditions for a Triangle Comparison Theorem, II James Hebda, SLU
Previous events…
Upcoming events…