A hybrid tabu search for batching and sequencing decisions in a single machine environment

• We study a batching and sequencing problem that exist on a single machine.
• A new MILP model provides optimal solutions for small size instances.
• A new hybrid tabu search (HTS) provides solutions for large size instances.
• EDD–EDD, EDD–BATCS and ATC–BATCS serve as testing tools.
• ATC–BATCS provides best initial solutions for the HTS.

This paper proposes a hybrid tabu search (HTS) to minimise the total weighted tardiness (TWT) for the batching and sequencing of jobs originating from incompatible families in which sequence dependent family setup times exist on single machine. The developed HTS includes distinguished features such as the strict arc based tabu classification along with dynamic tabu tenures, hybrid neighbourhood structures and iterative phases which consist of job and batch sequencing phases. The authors developed a testing methodology to determine the quality of the HTS solution. A mixed integer linear programing (MILP) model was developed to evaluate the optimality of the solution of the HTS for a small-size instance that consists of 640 problems. In addition, three dispatching rule heuristic combinations (EDD–EDD, EDD–BATCS and ATC–BATCS) were developed to test the HTS for large-size instances that deals with 1440 problems. The HTS provided comparable results with the MILP for small-size instances and outperformed the developed dispatching heuristics.