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

This paper develops an algorithmic approach for solving a particular capacitated production scheduling problem that appears in paper forming and other industries employing similar manufacturing processes. The paper process involves the heating, forming, and cooling of paper products. The manufacturing equipment (called a thermoformer) permits the concurrent production of different products. All products are produced under heat and pressure in a mold. The company can select any combination of molds for use in the thermoformer at a given time. A thermoformer holds a specific number of molds. Once the desired molds have been put into the thermoformer's slots, it is heated to the production temperature and production begins. Operation of the thermoformer involves cycling between loading of stock material and removing formed products. In a given run a number of production cycles, or strokes, depends on the products being produced and the quantity needed for each product. The machine will continue these strokes until the demand for one or more of the products is fulfilled. At this point, the equipment is stopped and cooled to permit changing the molds loaded in the thermoformer. After a mold change, the thermoformer must be warmed back up to the operating temperature before production can be resumed. Cool-down/warm-up time and the time to change molds yield a function for ``downtime per run''. The objective is to determine the number of molds for each product in the thermoformer for each run in such a way that the sum of total active production time and total downtime will be minimized. This problem may be characterized as a nonlinear integer optimization problem. To solve it, the authors develop an heuristic algorithm based on implicit enumeration. The proposed algorithm incorporates a fathoming technique and additional restrictions to reduce the portion of the solution set enumerated. The test problems for the computational experiments were generated from actual data from a paper product manufacturer. The proposed heuristic algorithm is shown to construct production schedules that exceeded the true optimal by no more than 5\%.