State Dependent Priority Rules for Scheduling

Abstract

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. The latter two enhancements of the myopic dispatching rules are implemented using rolling forecasting and planning horizons. In our large scale tests in static flow shops and dynamic job shops, the Apparent Urgency and CoverT rules with the static lead time estimates surpassed the competing rules in weighted tardiness performance. The new priority-based lead time estimates improved both rules vis-a-vis the conventional method, making CoverT best in heavily loaded shops. The periodic adjustment of the slack evaluation parameters did not, however, lead to a consistent improvement of the rules' performance. The coordination of the Apparent Urgency rule, achieved through the lead time iteration procedure, proved paramount for a superior performance in weighted tardiness and combined schedule costs. The experiment with continuously updated information, the average anticipated urgency of the jobs in the machine queues, as a part of the AU priority index was not as successful. This probing of job's relative priority on the next machine should prevent temporary congestion, but it was ineffective in long run. The robustness of the new rules was tested against errors in the processing time estimates and also in terms of other criteria such as the number of tardy jobs, work-in-process inventory, and maximal tardiness cost with extremely good results. Further extensions of state dependent rules are specified to multi-objective, multi-resource scheduling using composite priority indexes and to dynamic lot sizing problems in closed job shops. Applications in developing incentive-compatible priority rules and in supporting diagnostic routines of scheduling expert systems are discussed.