Solution Approaches for the Parallel Identical Machine Scheduling Problem with Sequence Dependent Setups

摘要

The setup scheduling problem is the problem of determining the sequence of multiple products produced on one or more resources/machines. The sequence-dependent setup scheduling problem is more difficult than the setup scheduling problem and extends it by incorporating different setup costs or times for each product, based on the product for which the resources were set up last. When producing multiple products on limited-capacity resources, minimizing the earliness and tardiness of product delivery is an important scheduling objective in the just-in-time (JIT) environment. Items produced too early incur holding costs, while items produced too late incur costs in the form of dissatisfied customers. This research compares the efficacy of a new network- based mixed-integer programming (MIP) formulation to an existing mixed-integer formulation for both the tardiness and the earliness/tardiness problems. An effective ET heuristic is also developed for earliness/tardiness problems too large to be solved efficiently by the MIP formulation. The presented MIP formulation provides a unique and useful method of conceptualizing and modeling a practical, yet difficult, problem within industry. This research shows that the new MIP model is much more efficient in terms of computation time for multi- machine problems than another known generalized formulation of these problems.