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 for 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. Tardiness is also an important objective when products are simply needed by a specific time.; 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 the new MIP model is much more efficient in terms of computation time for multi-machine problems in comparison with the Zhu and Heady generalized formulation of these problems. The structure of this model, which adapted a network-based traveling salesman problem (TSP) structure to multiple machines, enables it to function as a new benchmark for future model improvements. This problem structure enabled CPLEX MIP software to solve problems with a greater number of machines increasingly faster. The mixed-integer nature of the formulation allows the solution of this class of problems by companies with any one of a number of commonly available integer programming software packages. The heuristic algorithm provides another effective tool in solving larger problems of this class where the MIP formulations become computationally too difficult to solve in a reasonable amount of time.