Mixed-integer linear programming monolithic formulations for lot-sizing and scheduling of single-stage batch facilities

MARCHETTI, PABLO A.; MÉNDEZ, CARLOS A.; CERDÁ, JAIME

INDUSTRIAL & ENGINEERING CHEMICAL RESEARCH

AMER CHEMICAL SOC

Año: 2010 vol. 49 p. 6482 - 6498

0888-5885

This paper presents a pair of mixed-integer linear programming (MILP) continuous-time formulations for the simultaneous lot-sizing and scheduling of single-stage multiproduct batch facilities. Both approaches can handle multiple customer orders per product at different due dates as well as variable processing times. To match product demands, several batches can be allocated to a single requirement and, at the same time, a single batch may be used to satisfy multiple orders. Through a novel procedure, a predefined set of batches for each order with enough elements to guarantee optimality is generated. The two proposed formulations deal with batch sequencing decisions in a different manner. One of them rigorously arranges individual batches assigned to the same unit, while the other sequences clusters of batches sharing the same product and due date, and processed in the same equipment item. Grouping batches into clusters seeks to reduce the number of product changeovers. The final contents of clusters are model decisions. Powerful symmetry breaking constraints based on allocation variables to avoid redundant solutions were also developed. Three cases studies involving up to 56 batches have been solved. The two formulations provide very good results at quite competitive CPU times when compared with prior monolithic techniques. Moreover, the approximate cluster-based method was able to solve very large problems in an efficient manner. It was validated by comparing its results with the ones provided by the rigorous model.