Parallel-machine scheduling to minimize overtime and waste costs

This article considers scheduling products in a parallel, non-identical machine environment subject to sequence-dependent setup costs and sequence-dependent setup times, where production waste and processing time of a product depend on feasible machine assignments. A Mixed-Integer Programming (MIP) formulation is developed that captures trade-offs between overtime labor costs and waste costs. Two solution procedures are developed to address large problem instances. One procedure is an algorithm that determines a vector of product-to-machine assignments that assists an MIP solver to find an initial feasible solution. The second procedure is a decomposition heuristic that iteratively solves a relaxed subproblem and uses the subproblem solution to fix assignment variables in the main MIP formulation. In addition, bounds on the quality of solutions found using the decomposition heuristic are presented. Experiments are conducted that show the developed formulation outperforms more traditional scheduling objectives with respect to the waste and overtime labor costs. Additional experimentation investigates the effects that problem parameter values have on total waste and labor costs, performance of the approaches, and the use of overtime labor.