Tactically delayed scheduling in single-machine and resource-constrained job shops.

摘要

This research investigates the importance of tactical delays (TD) in dynamic job shop scheduling with both regular and non-regular objective functions. Branch-and-bound procedures were developed for both single machine and resource constrained job shops. Three environmental factors were considered: shop utilization, due date tightness and due date arbitrariness. For some dynamic tardiness problems, the optimum schedules are TD schedules. The study shows that TD schedules are important when due dates are highly arbitrary and when shop utilization is low. The results also show that optimum schedules are TD schedules in all the cases when performance measure is non-regular, early/tardy cost.; A new decision theory based scheduling heuristic (DT) was developed for generating TD schedules. Several variations of the DT method were proposed for single machine and resource constrained job shops. Simulation results indicated that the DT heuristic was the best compared to some well known dispatching rules, such as EDD and ATC, in all cases. Two versions of filtered beam search method were also tested in the simulation. Although they performed better than the DT heuristic in some cases, due to the computational requirement of the filtered beam search procedure, the DT method is still an efficient and effective approach for the problems studied.