A mathematical model for selecting mixed models with due dates

The performance of a sequencing procedure to smooth out the fluctuating workload (and part utilization) on a paced assembly line relies heavily on the average load of the model mixes chosen from the order-bank. Meanwhile, the due-dates of orders may conflict with this production-centred goal. This study proposes a mathematical model to select a fixed number of jobs while minimizing the total cost of producing them at the next period and satisfying capacity (right-hand side) limits at stations. A branch-and-bound procedure, which employs some dominance criteria, is proposed to provide optimal solutions. Pairwise interchange heuristics are developed to improve the initial solution, which is optimum but not feasible. Computational results show that optimal solutions can be obtained very efficiently for 100-job and 10-station problems. A three-factor experiment indicates that the RHS limit is the only significant parameter on the performance of the procedures. For over 1000-job problems, the best heuristic finds the optimal solution most of the time and, in the worst case, yields a solution that is 7.38% from optimality.