Hierarchical composition heuristic for asymmetric sequence dependent single machine scheduling problems

We present the Hierarchical Composition (HICOM) heuristic procedure for single machine scheduling with sequence dependent setups that minimizes the total setup time. The heuristic is a two-stage procedure that takes advantage of the natural product groupings, and can be used in a group technology environment. Computational results show that HICOM requires negligible solution time for all cases tested with various sizes. More importantly, when benchmarked against the general purpose solver CPLEX, HICOM shows advantages in both CPU time and solution quality for large size problems. Thus, HICOM is highly valuable in practice when quick and good solutions are preferred in scheduling dynamics under the just-in-time lean manufacturing environment. Furthermore, when commercial software is not available, as often is the case for small to medium manufacturers, HICOM becomes a viable option because it is easy to understand and implement.