State Dependent Priority Rules for Scheduling.
CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST
Pagination or Media Count:
The purpose of this thesis is to enhance the priority setting procedures for job shop scheduling systems. The new state dependent priority rules extend the concept of a myopic dispatching heuristic by allowing a wide choice of forecasting and planning horizons and by encompassing indirect or direct load information, even performance feedback, while maintaining the flexibility and robustness of the dispatching approach. Preliminary results are proven in the special case of proportionate flow shops with pre-emption. Many optimal rules for lateness and tardiness problems are extended from the single machine case to flow shops. Appropriate lead time estimation used in setting operation due dates can be shown to guarantee the achievement of a global optimum when applying a myopic rule locally. In more general job shop environments, we study scheduling with due dates when jobs have different tardiness penalties. Advanced slack evaluation methods have been developed for our Apparent Urgency rule and for the modified CoverT rule. First, waiting line analysis furnishes the use of indirect load information, such as the distribution of the jobs weights and processing times, in assigning static priority-based waiting time estimates for each operation. Second, the waiting time estimation and look-ahead parameters of the rules are further adjusted on the basis of direct, periodically updated state information, such as the anticipated queue lengths in the shop. Third, an iterative scheme is used to revise new lead time estimates based on the jobs realized waiting times in successive schedules. This lead time iteration provides also feedback from the performance of the rule for the coordination of the priority assignments.
- Operations Research