Sequencing heuristic for scheduling jobs with dependent setups in a manufacturing system

摘要

In this paper we discuss a single-machine scheduling problem with machine maintenance. In many production systems, the sequence-dependent setup time of a job cannot be ignored when a switch between two different jobs occurs. In our research, we develop a heuristic to minimize the completion time, or equivalently the total setup time subject to maintenance and due dates. The heuristic consists of three procedures: the initialization procedure, the Stinson heuristic procedure and the iterative procedure. Computational performance of the heuristic is evaluated by comparing its solution with the solution of the branch-and-bound algorithm. The performance of the heuristic on various sizes problems is provided.