Single-machine scheduling with family setup times in a manufacturing system

This study considers a single-machine scheduling problem with sequence-dependent setup times. Specifically, this article discusses the problem with several families. In this research, the study assumes that the job being processed must be stopped if workers do not want to work at the weekend. This article calls the weekend period ‘vacation’. Owing to complications in the production system, the setup time will be affected if the setup time is interrupted due to vacations. An efficient heuristic is developed to solve the problem of minimizing the maximum tardiness, subject to the family-setup time and vacation constraints. The article presents a heuristic to solve large-sized problems. A branch-and-bound algorithm that utilizes several theorems is also proposed to find the optimal schedules for the problem. Computational results are provided to demonstrate the effectiveness of the heuristic.