An heuristic algorithm for a multi-product, single machine capacitated production scheduling problem

This paper develops a technique for solving a capacitated production scheduling problem representative of a paper forming manufacturing process. The process involves equipment set ups for which down time has both fixed and variable components. An objective of minimizing the total time required to produce given orders for each of the products is considered. The scheduling problem may be characterized as a non-linear, integer, optimization problem. While there is a variety of literature available concerning optimization and scheduling theory, very little of it is directly applicable to the problem investigated here. The algorithmic methods (and associated computer programs) that were used in this research were developed specifically to solve these problems in reasonable times. The proposed algorithm is shown to generate production schedules that exceeded the true optimal by no more than 5%.