A complex time based construction heuristic for batch scheduling problems in the chemical industry. (English) Zbl 1103.90041
Summary: We investigate a heuristic for batch processing problems occurring in the chemical industry, where the objective is to minimize the makespan. Usually, this kind of problem is solved using mixed-integer linear programs. However, due to the large number of binary variables good results within a reasonable computational time could only be obtained for small instances.
We propose an iterative construction algorithm which alternates between construction and deconstruction phases. Moreover, we suggest diversification and intensification strategies in order to obtain good suboptimal solutions within moderate running times. Computational results show the power of this algorithm.
We propose an iterative construction algorithm which alternates between construction and deconstruction phases. Moreover, we suggest diversification and intensification strategies in order to obtain good suboptimal solutions within moderate running times. Computational results show the power of this algorithm.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B30 | Production models |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Blömer, F.; Günther, H., Scheduling of a multi-product batch process in the chemical industry, Computers in Industry, 36, 245-259 (1998) |
| [2] | F. Blömer, H. Günther, Numerical evaluation for scheduling chemical batch processes, Discussion Paper 1999/05, TU Berlin, 1999.; F. Blömer, H. Günther, Numerical evaluation for scheduling chemical batch processes, Discussion Paper 1999/05, TU Berlin, 1999. |
| [3] | Blömer, F.; Günther, H., LP-based heuristics for scheduling chemical batch processes, International Journal of Production Research, 38, 5, 1029-1051 (2000) · Zbl 0949.90613 |
| [4] | Burkard, R.; Hujter, M.; Klinz, B.; Rudolf, R.; Wennink, M., A process scheduling problem arising from chemical production planning, Optimization Methods and Software, 10, 175-196 (1998) · Zbl 0941.90034 |
| [5] | Burkard, R.; Kocher, M.; Rudolf, R., Rounding strategies for mixed integer programs arising from chemical production planning, Yugoslav Journal of Operations Research, 8, 9-23 (1998) · Zbl 1009.90075 |
| [6] | Burkard, R.; Fortuna, T.; Hurkens, C., Makespan minimization for chemical batch processes using non-uniform time grids, Computers and Chemical Engineering, 26, 1321-1332 (2002) |
| [7] | R. Burkard, J. Hatzl, Review, extensions and computational comparison of MILP formulations for scheduling of batch processes, Computers and Chemical Engineering, in press.; R. Burkard, J. Hatzl, Review, extensions and computational comparison of MILP formulations for scheduling of batch processes, Computers and Chemical Engineering, in press. |
| [8] | J. Hatzl, Makespan Minimization for Batch Processes, Ph.D. Thesis, Institute of Optimization, Dynamical Systems and Discrete Mathematics, Graz University of Technology, 2004.; J. Hatzl, Makespan Minimization for Batch Processes, Ph.D. Thesis, Institute of Optimization, Dynamical Systems and Discrete Mathematics, Graz University of Technology, 2004. |
| [9] | Ierapetritou, M.; Floudas, C., Effective continuous-time formulation for short-term scheduling. 1. Multipurpose batch processes, Industrial and Engineering Chemistry Research, 37, 4341-4359 (1998) |
| [10] | Ierapetritou, M.; Floudas, C., Effective continuous-time formulation for short-term scheduling. 2. Continuous and semicontinuous processes, Industrial and Engineering Chemistry Research, 37, 4360-4374 (1998) |
| [11] | Kallrath, J., Planning and scheduling in the process industry, OR Spectrum, 24, 219-250 (2002) · Zbl 1007.90506 |
| [12] | Kondili, E.; Pantelides, C.; Sargent, R., A general algorithm for short-term scheduling of batch operations—I. MILP formulation, Computers and Chemical Engineering, 17, 211-227 (1993) |
| [13] | Mockus, L.; Reklaitis, G., Mathematical programming formulation for scheduling of batch operations based on nonuniform time discretization, Computers and Chemical Engineering, 21, 1147-1156 (1997) |
| [14] | Neumann, K.; Schwindt, C.; Trautmann, N., Advanced production scheduling for batch plants in process industries, OR Spectrum, 24, 251-279 (2002) · Zbl 1007.90505 |
| [15] | C. Pantelides, Unified frameworks for optimal process planning and scheduling, in: Proceedings 2nd Conference Foundations of Computer Aided Process Operations, 1994, pp. 253-274.; C. Pantelides, Unified frameworks for optimal process planning and scheduling, in: Proceedings 2nd Conference Foundations of Computer Aided Process Operations, 1994, pp. 253-274. |
| [16] | Papageorgiou, L.; Pantelides, C., A hierarchical approach for campaign planning of multi-purpose batch plants, Computers and Chemical Engineering, 17, 27-32 (1993) |
| [17] | (Reklaitis, G.; Sunol, A.; Rippin, D.; Hortascu, Ö., Batch processing systems engineering. Batch processing systems engineering, NATO ASI series (1996), Springer-Verlag) |
| [18] | Sahinidis, N.; Grossmann, I., MINLP model for cyclic multiproduct scheduling on continuous parallel lines, Computers and Chemical Engineering, 15, 85-103 (1991) |
| [19] | Sahinidis, N.; Grossmann, I., Reformulation of multiperiod MILP models for planning and scheduling of chemical processes, Computers and Chemical Engineering, 15, 255-272 (1991) |
| [20] | Schilling, G.; Pantelides, C., A simple continuous-time process scheduling formulation and a novel solution algorithm, Computers and Chemical Engineering, 20, 1221-1226 (1996) |
| [21] | G. Schilling, Algorithms for Short-term and Periodic Process Scheduling and Rescheduling, Ph.D. Thesis, Department of Chemical Engineering and Chemical Technology, Imperial College of Science, Technology and Medicine, University of London, 1997.; G. Schilling, Algorithms for Short-term and Periodic Process Scheduling and Rescheduling, Ph.D. Thesis, Department of Chemical Engineering and Chemical Technology, Imperial College of Science, Technology and Medicine, University of London, 1997. |
| [22] | Schwindt, C.; Trautmann, N., Batch scheduling in process industries: An application of resource-constrained project scheduling, OR Spectrum, 22, 501-524 (2000) · Zbl 0985.90042 |
| [23] | Shah, N.; Pantelides, C.; Sargent, R., A general algorithm for short-term scheduling of batch operations—II. Computational issues, Computers and Chemical Engineering, 17, 229-244 (1993) |
| [24] | Shah, N.; Pantelides, C.; Sargent, R., Optimal periodic scheduling of multipurpose batch plants, Annals of Operations Research, 42, 193-228 (1993) · Zbl 0775.90219 |
| [25] | Vin, J.; Ierapetritou, M., A new approach for efficient rescheduling of multiproduct batch plant, Industrial and Engineering Chemistry Research, 39, 4228-4238 (2000) |
| [26] | H. Westenberger, J. Kallrath, Formulation of a job shop problem in process industry, Unpublished working paper, Bayer AG, Leverkusen, 1994.; H. Westenberger, J. Kallrath, Formulation of a job shop problem in process industry, Unpublished working paper, Bayer AG, Leverkusen, 1994. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
