Job shop scheduling heuristics and frequency of scheduling

Abstract

This paper presents a job scheduling problem. Two important aspects are included in the subsequent analysis. The first is the dynamic nature whereby new jobs arrive to be included intermittently through time. The second is the uncertainty, or error in estimating process times, and the likelihood of machine breakdown. An experiment is presented which shows the performance of a number of heuristics in the form of dispatching disciplines under different scheduling conditions which are determined by the scheduling period and the level of uncertainty in the process times and machine breakdowns. Various different measures of performance which could be of importance to management are considered. These include mean ratio of flow time to process time, mean queueing time, mean lateness, percentage of jobs late and net CPU times required to generate schedules in the simulation process.

Results are presented showing the relationship between the performance of the heuristics relative to the different measures and the rescheduling period. These are discussed in the more general managerial context.