Applying a modified coefficient reduction method to a dynamic production scheduling model

This paper develops and tests a short-run production scheduling model for process industry application. The authors consider a multi-product, multi-period environment, where a subset of the products can be produced on each of the production lines at a fixed rate per period. The resulting 0-1 mixed integer programming problem is difficult to solve using commercial optimization software. A preprocessing method based on coefficient reduction was modified to exploit the problem structure. This preprocessing tightens the problem prior to solution by a commercial branch-and-bound code. The remaining duality gap is defined as the percentage difference between the best feasible value and the tightest bound found, i.e. it is the maximum improvement in objective function value that can still be expected. Gaps of less than 4% were found in all test problems when production losses were zero. With the inclusion of production losses, preprocessing led to about a 50% reduction in the remaining gaps. Additional computational studies found that this approach can process constraints having up to 80-110 variables. Further research is suggested to investigate the computational effectiveness of other solution approaches.