Centralized Scheduling and Priority Implementation Heuristics for a Dynamic Job Shop Model

The problem considered is the scheduling of a job shop with job due dates, intermittent job arrivals, and statistical processing times. Centralized scheduling uses a sequence of static problems for generating priorities at review times. A multi-pass heuristic program, which has proven effective in earlier research, is applied to the up-dated static scheduling problem at each review time. A procedure is proposed for implementing priorities on the shop floor between review times. The procedure is expressly designed to integrate the scheduling of newly arriving jobs to modify the schedule. In simulation experiments using tardiness statistics for evaluation, centralized scheduling and the proposed implementation procedure proved to be an extremely effective combination. Comparison with another procedure that gives the centralized schedule precedence over new arrivals indicates the importance of the implementation procedure when periodic centralized scheduling is used in a dynamic situation.