Scheduling with sequence dependent setup times

When setup times are significant and sequence dependent, they need to be given special consideration in the scheduling process to ensure good performance in terms of resource utilization. This dissertation addresses three different scheduling problems involving sequence dependent setups and due date related performance criteria. The setup matrices considered have a special structure which is often seen in process industries.; A simple single machine dynamic scheduling problem is defined. Alternative scheduling rules are developed using Markov Decision Processes (MDP). A generalized scheduling policy is established based on the optimal results.; Necessary conditions to minimize the maximum lateness are determined for a static single machine problem with sequence dependent setups. An effective and efficient solution procedure composed of a sequence of two neighborhood search strategies is developed to solve this problem.; The generalized scheduling policy developed for dynamic problems is combined with a forecasting mechanism to utilize the global shop floor information at local dispatching decisions. This policy is incorporated into the Virtual Factory, a job shop scheduling system developed at North Carolina State University. The performance is significantly better than that of existing methods.