×

zbMATH — the first resource for mathematics

Mixed integer linear programming in process scheduling: modeling, algorithms, and applications. (English) Zbl 1091.90055
Summary: This paper reviews the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. We focus on the short-term scheduling of general network represented processes. First, the various mathematical models that have been proposed in the literature are classified mainly based on the time representation. Discrete-time and continuous-time models are presented along with their strengths and limitations. Several classes of approaches for improving the computational efficiency in the solution of MILP problems are discussed. Furthermore, a summary of computational experiences and applications is provided. The paper concludes with perspectives on future research directions for MILP based process scheduling technologies.

MSC:
90C11 Mixed integer programming
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Applequist, G., O. Samikoglu, J. Pekny, and G. Reklaitis. (1997). ”Issues in the Use, Design and Evolution of Process Scheduling and Planning Systems.” ISA Transactions 36, 81–121.
[2] Bassett, M.H., P. Dave, F.J.D. III, G.K. Kudva, J.F. Pekny, G.V. Reklaitis, S. Subrahmanyam, D.L. Miller, and M.G. Zentner. (1996a). ”Perspectives on Model Based Integration of Process Operations.” Computers & Chemical Engineering 20, 821–844.
[3] Bassett, M.H., J.F. Pekny, and G.V. Reklaitis. (1996b). ”Decomposition Techniques for the Solution of Large-Scale Scheduling Problems.” AIChE Journal 42, 3373–3387.
[4] Blömer, F. and H.-O. Günther. (2000). ”LP-Based Heuristics for Scheduling Chemical Batch Processes.” International Journal of Production Research 38, 1029–1051. · Zbl 0949.90613
[5] Bok, J. and S. Park. (1998). ”Continuous-Time Modeling for Short-Term Scheduling of Multipurpose Pipeless Plants.” Industrial & Engineering Chemistry Research 37, 3652–3659.
[6] Bowman, E.H. (1959). ”The Schedule-Sequencing Problem.” Operations Research 7, 621–624. · Zbl 1255.90059
[7] Burkard, R.E., T. Fortuna, and C.A.J. Hurkens. (2002). ”Makespan Minimization for Chemical Batch Processes Using Non-Uniform Time Grids.” Computers & Chemical Engineering 26, 1321–1332.
[8] Castro, P., A.P.F.D. Barbosa-Póvoa, and H. Matos. (2001). ”An Improved RTN Continuous-Time Formulation for the Short-Term Scheduling of Multipurpose Batch Plants.” Industrial & Engineering Chemistry Research 40, 2059–2068.
[9] Castro, P., H. Matos, and A.P.F.D. Barbosa-Póvoa. (2002). ”Dynamic Modeling and Scheduling of an Industrial Batch System.” Computers & Chemical Engineering 26, 671–686.
[10] Cerdá, J., G.P. Henning, and I.E. Grossmann. (1997). ”A Mixed-Integer Linear Programming Model for Short-Term Scheduling of Single-Stage Multiproduct Batch Plants with Parallel Lines.” Industrial & Engineering Chemistry Research 36, 1695–1707.
[11] Dedopoulos, I.T. and N. Shah. (1995). ”Optimal Short-Term Scheduling of Maintenance and Production for Multipurpose Plants.” Industrial & Engineering Chemistry Research 34, 192–201.
[12] Dimitriadis, A.D., N. Shah, and C.C. Pantelides. (1997). ”RTN-Based Rolling Horizon Algorithms for Medium Term Scheduling of Multipurpose Plants.” Computers & Chemical Engineering 21, S1061–S1066.
[13] Elkamel, A. and G. Al-Enezi. (1998). ”Structured Valid Inequalities and Separation in Optimal Scheduling of the Resource-Constrained Batch Chemical Plant.” Mathematical Engineering in Industry 6, 291– 318. · Zbl 0913.90169
[14] Elkamel, A., M. Zentner, J.F. Pekny, and G.V. Reklaitis. (1997). ”A Decomposition Heuristic for Scheduling the General Batch Chemical Plant.” Engineering Optimization 28, 299–330.
[15] Floudas, C.A. (1995). Nonlinear and Mixed-Integer Optimization. Oxford University Press. · Zbl 0886.90106
[16] Floudas, C.A. and X. Lin. (2004). ”Continuous-Time versus Discrete-Time Approaches for Scheduling of Chemical Processes: A Review.” Computers & Chemical Engineering 28, 2109–2129.
[17] Garey, M.R. and D.R. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. · Zbl 0411.68039
[18] Georgiadis, M.C., L.G. Papageorgiou, and S. Macchietto. (2000). ”Optimal Cleaning Policies in Heat Exchanger Networks under Rapid Fouling.” Industrial & Engineering Chemistry Research 39, 441–454.
[19] Glismann, K. and G. Gruhn. (2001). ”Short-Term Scheduling and Recipe Optimization of Blending Processes.” Computers & Chemical Engineering 25, 627–634.
[20] Glover, F. (1975). ”Improved Linear Integer Programming Formulations of Nonlinear Integer Problems.” Management Science 22, 455–460. · Zbl 0318.90044
[21] Grossmann, I.E., I. Quesada, R. Raman, and V.T. Voudouris. (1996). ”Mixed-Integer Optimization Techniques for the Design and Scheduling of Batch Processes.” In G. V. Reklaitis, A. K. Sunol, D. W. T. Rippin and O. Hortacsu (ed.), Batch Processing Systems Engineering, Berlin: Springer, pp. 451– 494.
[22] Harjunkoski, I. and I.E. Grossmann. (2001). ”A Decomposition Approach for the Scheduling of a Steel Plant Production.” Computers & Chemical Engineering 25, 1647–1660.
[23] Hui, C. and A. Gupta. (2001). ”A Bi-index Continuous-Time Mixed-Integer Linear Programming Model for Single-Stage Batch Scheduling with Parallel Units.” Industrial & Engineering Chemistry Research 40, 5960–5967.
[24] Hui, C., A. Gupta, and H.A.J. van der Meulen. (2000). ”A Novel MILP Formulation for Short-Term Scheduling of Multi-Stage Multi-Product Batch Plants with Sequence-Dependent Constraints.” Computers & Chemical Engineering 24, 2705–2717.
[25] Ierapetritou, M.G. and C.A. Floudas. (1998a). ”Effective Continuous-Time Formulation for Short-Term Scheduling: 1. Multipurpose Batch Processes.” Industrial & Engineering Chemistry Research 37, 4341–4359.
[26] Ierapetritou, M.G. and C.A. Floudas. (1998b). ”Effective Continuous-Time Formulation for Short-Term Scheduling: 2. Continuous and Semi-Continuous Processes.” Industrial & Engineering Chemistry Research 37, 4360–4374.
[27] Ierapetritou, M.G. and C.A. Floudas. (2001). Comments on ”An Improved RTN Continuous-Time Formulation for the Short-term Scheduling of Multipurpose Batch Plants.” Industrial & Engineering Chemistry Research 40, 5040–5041.
[28] Ierapetritou, M.G., T.S. Hené, and C.A. Floudas. (1999). ”Effective Continuous-Time Formulation for Short-Term Scheduling: 3. Multiple Intermediate Due Dates.” Industrial & Engineering Chemistry Research 38, 3446–3461.
[29] Janak, S.L., X. Lin, and C.A. Floudas. (2004). ”Enhanced Continuous-Time Unit-Specific Event-Based Formulation for Short-Term Scheduling of Multipurpose Batch Processes: Resource Constraints and Mixed Storage Policies.” Industrial & Engineering Chemistry Research 43, 2516–2533.
[30] Karimi, I.A. and C.M. McDonald. (1997). ”Planning and Scheduling of Parallel Semi-Continuous Processes. 2. Short-Term Scheduling.” Industrial & Engineering Chemistry Research 36, 2701–2714.
[31] Kondili, E., C.C. Pantelides, and R.W.H. Sargent. (1988). ”A General Algorithm for Scheduling Batch Operations.” In Proceedings of the Third International Symposium on Process Systems Engineering, Sydney, Australia, pp. 62–75.
[32] Kondili, E., C.C. Pantelides, and R.W.H. Sargent. (1993). ”A General Algorithm for Short-Term Scheduling of Batch Operations - I. MILP Formulation.” Computers & Chemical Engineering 17, 211– 227.
[33] Ku, H. and I.A. Karimi. (1988). ”Scheduling in Serial Multiproduct Batch Processes with Finite Interstage Storage: A Mixed Integer Linear Programming Formulation.” Industrial & Engineering Chemistry Research 27, 1840–1848.
[34] Lamba, N. and I.A. Karimi. (2002a). ”Scheduling Parallel Production Lines with Resource Constraints. 1. Model Formulation.” Industrial & Engineering Chemistry Research 41, 779–789.
[35] Lamba, N. and I.A. Karimi. (2002b). ”Scheduling Parallel Production Lines with Resource Constraints. 2. Decomposition Algorithm.” Industrial & Engineering Chemistry Research 41, 790–800.
[36] Lee, K., S. Heo, H. Lee, and I. Lee. (2002). ”Scheduling of Single-Stage and Continuous Processes on Parallel Lines with Intermediate Due Dates.” Industrial & Engineering Chemistry Research 41, 58– 66.
[37] Lee, K., H.I. Park, and I. Lee. (2001). ”A Novel Nonuniform Discrete Time Formulation for Short-Term Scheduling of Batch and Continuous Processes.” Industrial & Engineering Chemistry Research 40, 4902–4911.
[38] Lin, X. and C.A. Floudas. (2001). ”Design, Synthesis and Scheduling of Multipurpose Batch Plants via an Effective Continuous-Time Formulation.” Computers & Chemical Engineering 25, 665–674.
[39] Lin, X., C.A. Floudas, S. Modi, and N.M. Juhasz. (2002). ”Continuous-Time Optimization Approach for Medium-Range Production Scheduling of a Multiproduct Batch Plant.” Industrial & Engineering Chemistry Research 41, 3884–3906.
[40] Majozi, T. and X.X. Zhu. (2001). ”A Novel Continuous-Time MILP Formulation for Multipurpose Batch Plants. 1. Short-Term Scheduling.” Industrial & Engineering Chemistry Research 40, 5935–5949.
[41] Manne, A.S. (1960). ”On the Job-Shop Scheduling Problem.” Operations Research 8, 219–223.
[42] Maravelias, C.T. and I.E. Grossmann. (2003). ”A New General Continuous-Time State Task Network Formulation for Short-Term Scheduling of Multipurpose Batch Plants.” Industrial & Engineering Chemistry Research 42, 3056–3074.
[43] Méndez, C.A. and J. Cerdá. (2000a). ”Optimal Scheduling of a Resource-Constrained Multiproduct Batch Plant Supplying Intermediates to Nearby End-Product Facilities.” Computers & Chemical Engineering 24, 369–376.
[44] Méndez, C.A., G.P. Henning, and J. Cerdá. (2000b). ”Optimal Scheduling of Batch Plants Satisfying Multiple Product Orders with Different Due-Dates.” Computers & Chemical Engineering 24, 2223–2245.
[45] Méndez, C.A., G.P. Henning, and J. Cerdá. (2001). ”An MILP Continuous-Time Approach to Short-Term Scheduling of Resource-Constrained Multistage Flowshop Batch Facilities.” Computers & Chemical Engineering 25, 701–711.
[46] Mockus, J., W. Eddy, A. Mockus, L. Mockus, and R.V. Reklaitis. (1997). Bayesian Heuristic Approach to Discrete and Global Optimization: Algorithms, Visualization, Software, and Applications. Kluwer Academic Publishers. · Zbl 0864.65036
[47] Mockus, L. and G.V. Reklaitis. (1997). ”Mathematical Programming Formulation for Scheduling of Batch Operations Based on Nonuniform Time Discretization.” Computers & Chemical Engineering 21, 1147–1156.
[48] Mockus, L. and G.V. Reklaitis. (1999a). ”Continuous Time Representation Approach to Batch and Continuous Process Scheduling. 1. MINLP Formulation.” Industrial & Engineering Chemistry Research 38, 197–203.
[49] Mockus, L. and G.V. Reklaitis. (1999b). ”Continuous Time Representation Approach to Batch and Continuous Process Scheduling. 2. Computational Issues.” Industrial & Engineering Chemistry Research 38, 204–210.
[50] Moon, S. and A.N. Hrymak. (1999). ”Mixed-Integer Linear Programming Model for Short-Term Scheduling of a Special Class of Multipurpose Batch Plants.” Industrial & Engineering Chemistry Research 38, 2144–2150.
[51] Moon, S., S. Park, and W.K. Lee. (1996). ”New MILP Models for Scheduling of Multiproduct Batch Plants under Zero-Wait Policy.” Industrial & Engineering Chemistry Research 35, 3458–3469.
[52] Orçun, S., I.K. Altinel, and Ö Hortaçsu. (1999). ”Reducing the Integrality Gap with a Modified Re-Formulation Linearization Approach.” Computers & Chemical Engineering Supplement, pp. S539–S542.
[53] Orçun, S., I.K., Altinel, and Ö Hortaçsu. (2001). ”General Continuous Time Models for Production Planning and Scheduling of Batch Processing Plants: Mixed Integer Linear Program Formulations and Computational Issues.” Computers & Chemical Engineering 25, 371–389.
[54] Pantelides, C.C. (1993). ”Unified Frameworks for Optimal Process Planning and Scheduling.” In D.W.T. Rippin, J.C. Hale, and J. Davis (eds.), Proceedings of the Second International Conference on Foundations of Computer-Aided Process Operations, Crested Butte, Colorado, pp. 253–274.
[55] Pekny, J.F. and G.V. Reklaitis. (1998). ”Towards the Convergence of Theory and Practice: A Technology Guide for Scheduling/Planning Methodology.” In J.F. Pekny and G.E. Blau (eds.), Proceedings of the Third International Conference on Foundations of Computer-Aided Process Operations, Snowbird, Utah, pp. 91–111.
[56] Pekny, J.F. and M.G. Zentner. (1993). ”Learning to Solve Process Scheduling Problems: The Role of Rigorous Knowledge Acquisition Frameworks.” In D.W.T. Rippin, J.C. Hale, and J. Davis (eds.), Proceedings of the Second International Conference on Foundations of Computer-Aided Process Operations, Crested Butte, Colorado, pp. 275–309.
[57] Pinto, J.M. and I.E. Grossmann. (1995). ”A Continuous Time Mixed Integer Linear Programming Model for Short Term Scheduling of Multistage Batch Plants.” Industrial & Engineering Chemistry Research 34, 3037–3051.
[58] Pinto, J.M. and I.E. Grossmann. (1996). ”An Alternate MILP Model for Short-Term Scheduling of Batch Plants with Preordering Constraints.” Industrial & Engineering Chemistry Research 35, 338–342.
[59] Pinto, J.M. and I.E. Grossmann. (1998). ”Assignment and Sequencing Models for the Scheduling of Process Systems.” Annals of Operations Research 81, 433–466. · Zbl 0911.90220
[60] Pinto, J.M., A. Türkay, B. Bolio, and I.E. Grossmann. (1998). ”STBS: A Continuous-Time MILP Optimization for Short-Term Scheduling of Batch Plants.” Computers & Chemical Engineering 22, 1297–1308.
[61] Pritsker, A.A.B., L.J. Watters, and P.M. Wolfe. (1969). ”Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach.” Management Science 16, 93–108.
[62] Reklaitis, G.V. (1992). ”Overview of Scheduling and Planning of Batch Process Operations.” NATO Advanced Study Institute–Batch Process Systems Engineering, Antalya, Turkey.
[63] Rippin, D.W.T. (1993). ”Batch Process Systems Engineering: A Retrospective and Prospective Review.” Computers & Chemical Engineering 17, S1–S13.
[64] Sahinidis, N.V. and I.E. Grossmann. (1991b). ”Reformulation of Multiperiod MILP Models for Planning and Scheduling of Chemical Processes.” Computers & Chemical Engineering 15, 255–272.
[65] Schilling, G. (1997). ”Optimal Scheduling of Multipurpose Plants.” PhD thesis, University of London.
[66] Schilling, G. and C.C. Pantelides. (1996). ”A Simple Continuous-Time Process Scheduling Formulation and a Novel Solution Algorithm.” Computers & Chemical Engineering 20, S1221–S1226.
[67] Schilling, G. and C.C. Pantelides. (1996b). ”A Hybrid Branch and Bound Algorithm for Continuous-Time Process Scheduling Formulations.” AIChE 1996 Annual Meeting, Chicago, IL, November 1996, Paper 171d.
[68] Shah, N. (1998). ”Single- And Multisite Planning and Scheduling: Current Status and Future Challenges.” In J.F. Pekny and G.E. Blau (eds.), Proceedings of the Third International Conference on Foundations of Computer-Aided Process Operations, Snowbird, Utah, pp. 75–90.
[69] Shah, N., C.C. Pantelides, and R.W.H. Sargent. (1993). ”A General Algorithm for Short-Term Scheduling of Batch Operations-II. Computational Issues.” Computers & Chemical Engineering 17, 229– 244.
[70] Sherali, H.D. and W.P. Adams. (1994). ”A Hierarchy of Relaxations and Convex-Hull Characterizations for Mixed-Integer Zero-One Programming Problems.” Discrete Applied Mathematics 52, 83–106. · Zbl 0819.90064
[71] Wang, S. and M. Guignard. (2002). ”Redefining Event Variables for Efficient Modeling of Continuous-Time Batch Processing.” Annals of Operations Research 116, 113–126. · Zbl 1013.90058
[72] Wilkinson, S.J., A. Cortier, N. Shah, and C.C. Pantelides. (1996). ”Integrated Production and Distribution Scheduling on a European-Wide Basis.” Computers & Chemical Engineering 20, S1275–S1280.
[73] Wilkinson, S.J., N. Shah, and C.C. Pantelides. (1995). ”Aggregate Modelling of Multipurpose Plant Operation.” Computers & Chemical Engineering 19, S583–S588.
[74] Yee, K.L. and N. Shah. (1998). ”Improving the Efficiency of Discrete Time Scheduling Formulation.” Computers & Chemical Engineering 22, S403–S410.
[75] Yi, G., K. Suh, B. Lee, and E.S. Lee. (2000). ”Optimal Operation of Quality Controlled Product Storage.” Computers & Chemical Engineering 24, 475–480.
[76] Zentner, M.G., A. Elkamel, J.F. Pekny, and G.V. Reklaitis. (1998). ”A Language for Describing Process Scheduling Problems.” Computers & Chemical Engineering 22, 125–145.
[77] Zentner, M.G., J.F. Pekny, G.V. Reklaitis, and J.N.D. Gupta. (1994). ”Practical Considerations in Using Model-Based Optimization for the Scheduling and Planning of Batch/Semicontinuous Processes.” Journal of Process Control 4, 259–280.
[78] Zhang, X. (1995). ”Algorithms for Optimal Scheduling Using Nonlinear Models.” PhD thesis, University of London.
[79] Zhang, X. and R.W.H. Sargent. (1996). ”The Optimal Operation of Mixed Production Facilities–A General Formulation and Some Solution Approaches for the Solution.” Computers & Chemical Engineering 20, 897–904.
[80] Zhang, X. and R.W.H. Sargent. (1998). ”The Optimal Operation of Mixed Production Facilities–Extensions and Improvements.” Computers & Chemical Engineering 22, 1287–1295.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.