Multiple orders per job batch scheduling with incompatible jobs

The multiple orders per job (MOJ) scheduling problem is presented for the batch-processing environment such as that exemplified by diffusion ovens. A mixed-integer programming formulation is presented for the incompatible job family case wherein only jobs that belong to the same family may be grouped together in a production batch. This optimization formulation is tested through an extensive experimental design with the objective of minimizing total weighted tardiness (maximizing on-time delivery performance). Optimal solutions are achievable for this initial set of 6-to-12 order problems, but it is noted that the optimization model takes an unreasonable amount of computation time, which suggests the need for heuristic development to support the analysis of larger, more practical MOJ batch scheduling problems. A number of simple heuristic approaches are investigated in an attempt to find near-optimal solutions in a reasonable amount of computation time. It is seen that a combination of the heuristics produces near-optimal solutions for small order problems. Further testing proves that these heuristic combinations are the best for large order problems as well.