A heuristic scheduling procedure to minimize the total tardiness on a single machine with sequence-dependent setup time

Compared to the more traditional issues in supply chain such as inventory control or lot-sizing, supply chain scheduling issue gets increasing attention of supply chain management. This research considers a supply chain scheduling problem with setup time and converts it into a single machine scheduling problem with setup time. It is important because setup time takes up machine time and system resource and it gets more important in today's manufacturing environment. As this problem is NP-hard, this research develops a heuristic procedure, Family Cutting Algorithm, to minimize total tardiness of jobs in the system. The Family Cutting Algorithm generates a temporary schedule to estimate the impact of setup time to the system to determine whether or not a family splitting is necessary. The Family Cutting Algorithm is based on the adjacent pairwise interchange property, Wilkerson-Irwin algorithm, look-ahead concept, and Net Benefit of Relocation analysis. The performance of the proposed procedure is compared with Apparent Tardiness Cost with Setup (ATCS) procedure, which is known for effectively minimizing the total tardiness of a schedule with setup time. Except for the ATCS rule, there are no good priority rules for the scheduling problems with setup time. Test results show that the Family Cutting algorithm is better than ATCS in minimizing total tardiness.