A hybrid heuristic and linear programming approach to multi-product machine scheduling

A new heuristic approach is presented for scheduling economic lots in a multi-product single-machine environment. Given a pre-defined master sequence of product setups, an integer linear programming formulation is developed which finds an optimal subsequence and optimal economic lots. The model takes explicit account of initial inventories, setup times and allows setups to be scheduled at arbitrary epochs in continuous time, rather than restricting setups to a discrete time grid. We approximate the objective function of the model and solve to obtain an optimal capacity feasible schedule for the approximate objective. The approach was tested on a set of randomly generated problems, generating solutions that are on average 2.5% above a lower bound on the optimal cost. We also extend the approach to allow shortages.