Generalized Pinwheel Problem

Event Details
  • Date/Time:
    • Friday October 3, 2003
      11:00 am - 12:00 am
  • Location: Smith Executive Classroom, 755 Ferst Drive
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher
404.385.3102
Summaries

Summary Sentence: Generalized Pinwheel Problem

Full Summary: Generalized Pinwheel Problem

We consider a non-preemptive infinite-horizon scheduling problem with a single server and a fixed set of recurring jobs. Each job is characterized by two given positive numbers: the job duration and a maximum allowable time interval that can elapse between when the job is finished and started again. We study the feasibility of this problem and, if it is feasible, how to find a feasible schedule. We call this problem a Generalized Pinwheel Problem.

The Pinwheel Problem, studied by several authors over the last 15 years, is a particular case of our problem when all job durations are equal. Our original interest in the Generalized Pinwheel Problem was motivated by radar sensor management applications. However, this is a natural scheduling problem that has other engineering applications. The studies of the Pinwheel Problem were primarily motivated by satellite communication applications.

We show that if the Generalized Pinwheel Problem is feasible, there exists a periodic schedule for this problem. We also provide necessary conditions for the feasibility, formulate an algorithm based on dynamic programming, and, since under certain conditions this problem is NP-hard, formulate and study heuristic algorithms. In particular, we model the Generalized Pinwheel Problem as a Semi-Markov Decision Process. This representation provides natural necessary conditions for the feasibility and leads to the development of heuristic algorithms that, according to simulations, outperform other heuristics.

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:42am
  • Last Updated: Oct 7, 2016 - 9:52pm