Short-Term Scheduling in Multi-Stage Batch Plants through Lagrangean Decomposition

Wednesday, November 11, 2009: 1:45 PM
Lincoln E (Gaylord Opryland Hotel)

Georgios M. Kopanos, Chemical Engineering Department, Universitat Politècnica de Catalunya - ETSEIB, Barcelona, Spain
José Miguel Laínez, School of Chemical Engineering, Purdue University, West Lafayette, IN
Luis Puigjaner, Chemical Engineering Department, Universitat Politècnica de Catalunya - ETSEIB, Barcelona, Spain

Despite the considerable advances in production scheduling modeling and computational solution methods in recent years, there is still a significant gap between scheduling theory and its implementation in practice. Academic contributions are mainly tested on relatively small problems. However, industrial applications consist of a large number of batches and numerous processing stages and equipment units (Méndez et al., 2006). The multi-stage scheduling problem is strongly NP-hard, and contributions attempting its resolution by exact methods are still limited.

Typically, heuristics or meta-heuristic methods are currently used for solving large-scale industrial scheduling problems. These methods give feasible solutions with relatively low computational effort, however solution optimality is not guaranteed. Therefore, industrial operation becomes suboptimal, with the resulting loss of competitive advantage and potential profits. Another drawback of these methods is that it is often impossible to know how far the proposed solution is from the optimal one; a fact that makes them unreliable.

In this work, a continuous-time Mixed-Integer Linear Programming (MILP) model for the short-term scheduling in multi-stage batch plants is used. The MILP model accounts for ready unit times, release order times, sequence-dependent changeovers, transfer times between adjacent processing stages and different intermediates storage policies. A Lagrangean decomposition technique (Conejo et al., 2002) is applied to the MILP model in order to facilitate the resolution of real-world industrial cases. The proposed decomposition technique is thoroughly examined.

An industrial case study of a multi-product multi-stage pharmaceuticals batch plant is addressed in order to demonstrate the performance and the advantages of the proposed decomposition scheme. The pharmaceutical plant under study consists of 17 processing equipments. The numerous (30 to 50) final products require 5 to 6 processing stages. Sequence-dependent changeovers are permitted in most stages. It is noteworthy that changeovers are usually of the same order of magnitude or even larger than the processing times. The main optimization goal is the minimization of the makespan. Results obtained are discussed highlighting the advantages and the special characteristics of the proposed scheduling model.


Authors appreciate the financial support received from the Spanish Ministry of Education and Innovation (FPU grant) and "Generalitat de Catalunya" (FI programs).


Méndez, C.A., Cerdá, J., Grossmann, I.E., Harjunkoski, I., Fahl, M., 2006. State-of-the-art review of optimization methods for short-term scheduling of batch processes. Computers and Chemical Engineering 30, 913-946.

Conejo A.J., Nogales F.J. and Prieto F.J., 2002. A Decomposition Procedure Based on Approximate Newton Directions. Mathematical Programming 93, 495-551.

Extended Abstract: File Not Uploaded
See more of this Session: Planning & Scheduling I
See more of this Group/Topical: Computing and Systems Technology Division