*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
