Analysis of Scheduling and Frozen Intervals in Dynamic Rescheduling


This research presents a new rescheduling methodology that creates both efficient and stable schedule. This methodology is motivated by the fact that making changes to a schedule near the current time should be discouraged because the closer to the current time that changes have been applied, the higher the probability that the cost of making a change increases and the less stability that the system has. Instead of scheduling all unprocessed jobs every time a new condition occurs, only those scheduled beyond a specified time in the future will be rescheduled; and the new arrivals, if any, will be scheduled. The remaining jobs are untouched and are referred to as lying within the "frozen interval". The objective of this research is to study the effect of this frozen interval on the schedule performance under various environments. The schedule performance is represented by a multi-objective function that simultaneously addresses efficiency and stability. Efficiency is defined in terms of makespan and tardiness while stability is defined as a linear combination of the deviation between the original and revised job starting times and the penalty function associated with total deviation from the current time. A genetic local search scheduler is employed to obtain a good schedule. The results indicate that using frozen interval in rescheduling provides a better and more robust schedule.