Scheduling incompatible job families on a single machine: A two-level heuristic approach

We introduce a two-level heuristic approach for solving jobs originated from incompatible job families that aims to minimize the total weighted tardiness. At the first level, an apparent tardiness cost with setups (ATCS) for a single machine is developed. The second level, a tabu search (TS) heuristic is developed that uses the initial solution obtained by the ATCS and provides a better solution if it exist. Real industrial data is used to test and validate the proposed methodology. The results indicate that the suggested approach can provide solution in a reasonable good time that can be of use for the decision maker.