×

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. (English) Zbl 1251.90147

Summary: We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Ruiz, R.; Vazquez-Rodriguez, J., The hybrid flow shop scheduling problem, European Journal of Operational Research, 205, 1-18 (2010) · Zbl 1188.90110
[2] Ruiz, R.; Serifoglu, F.; Urlings, T., Modeling realistic hybrid flowshop scheduling problems, Computers & Operations Research, 35, 1151-1175 (2008) · Zbl 1180.90135
[3] Ribas, I.; Leisten, R.; Framinan, J., Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective, Computers & Operations Research, 37, 1439-1454 (2010) · Zbl 1183.90189
[4] Oguz, C.; Ercan, M.; Edwin Cheng, T.; Fung, Y., Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop, European Journal of Operational Research, 110, 390-403 (2003) · Zbl 1059.90072
[5] Ying, K.; Lin, S., Scheduling multistage hybrid flowshops with multiprocessor tasks by an effective heuristic, International Journal of Production Research, 13, 1, 3525-3538 (2009) · Zbl 1198.90217
[6] Sawik, T., An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers, Mathematical & Computer Modelling, 36, 461-471 (2002) · Zbl 1052.90038
[7] Wardono, B.; Fathi, Y., A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities, European Journal of Operational Research, 155, 380-401 (2004) · Zbl 1045.90035
[8] Wang, X.; Tang, L., A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers, Computers & Operations Research, 36, 907-918 (2009) · Zbl 1157.90429
[9] Grabowski, J.; Pempera, J., Sequencing of jobs in some production system, European Journal of Operational Research, 125, 3, 535-550 (2000) · Zbl 0967.90045
[10] Wang, Z.; Xing, W.; Bai, F., No-wait flexible flowshop scheduling with no-idle machines, Operations Research Letters, 33, 6, 609-614 (2005) · Zbl 1082.90042
[11] Yang, D.; Chern, M., A two-machine flowshop scheduling problem with limited waiting time constraints, Computers & Industrial Engineering, 28, 1, 63-70 (1995)
[12] Su, L., A hybrid two-stage flowshop with limited waiting time constraints, Computers & Industrial Engineering, 47, 409-424 (2003)
[13] Akkerman, R.; van Donk, D.; Gaalman, G., Influence of capacity- and time-constraint intermediate storage in two-stage food production systems, International Journal of Production Research, 45, 13, 2955-2973 (2007) · Zbl 1126.90339
[14] Low, C., Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines, Computers & Operations Research, 32, 2013-2025 (2005) · Zbl 1068.90060
[15] Kis, K.; Pesch, E., A review of exact solution methods for the non-preemptive multiprocessor flowshop problem, European Journal of Operational Research, 164, 592-608 (2005) · Zbl 1057.90015
[16] Floudas, C.; Lin, X., Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review, Computers & Chemical Engineering, 28, 2109-2129 (2004)
[17] Mendez, C.; Cerda, J.; Grossmann, I.; Harjunkoski, I.; Fahl, M., State-of-the-art review of optimization methods for short-term scheduling of batch processes, Computers & Chemical Engineering, 30, 913-946 (2006)
[18] Sundaramoorthy, A.; Maravelias, C., Modeling of storage in batching and scheduling of multistage processes, Computers & Chemical Engineering, 30, 913-946 (2006)
[19] Moon, S.; Park, S.; Kook Lee, W., Mixed-integer linear programming model for short-term scheduling of a special class of multipurpose batch plants, Industrial & Engineering Chemistry Research, 38, 2144-2150 (1999)
[20] Lee, D.; Vassiliadis, V.; Park, J., List-based threshold-accepting algorithm for zero-wait scheduling of multiproduct batch plants, Industrial & Engineering Chemistry Research, 41, 6579-6588 (2002)
[21] Liu, Y.; Karimi, I., Scheduling multistage batch plants with parallel units and no interstage storage, Computers & Chemical Engineering, 32, 671-693 (2008)
[22] Liu, B.; Wang, L.; Qian, B.; Jin, Y., An effective hybrid particle swarm optimization for batch scheduling of polypropylene processes, Computers & Chemical Engineering, 34, 518-528 (2010)
[23] Kondili, E.; Pantelides, C.; Sargent, R., A general algorithm for short-term scheduling of batch operations-I. MILP formulation, Computers & Chemical Engineering, 17, 2, 211-227 (1993)
[24] Shah, N.; Pantelides, C.; Sargent, R., A general algorithm for short-term scheduling of batch operations-II. Computational issues, Computers & Chemical Engineering, 17, 2, 229-244 (1993)
[25] Blomer, F.; Gunther, H., LP-based heuristics for scheduling chemical batch processes, International Journal of Production Economics, 38, 5, 1029-2051 (2000) · Zbl 0949.90613
[26] Maravelias, C.; Grossmann, I., Minimization of the makespan with a discrete-time state-task network formulation, Industrial & Engineering Chemistry Research, 42, 6252-6257 (2003)
[27] Burkard, R.; Hatzl, J., Review, extensions and computational comparison of MILP formulations for scheduling of batch processes, Computers & Chemical Engineering, 29, 1752-1769 (2005)
[28] Moon, S.; Hrymak, A., New MILP models for scheduling of multiproduct batch plants under zero-wait policy, Industrial & Engineering Chemistry Research, 35, 3458-3469 (1996)
[29] Lamba, N.; Karimi, I., Scheduling parallel production lines with resource constraints. 1. Model formulation, Industrial & Engineering Chemistry Research, 41, 779-789 (2002)
[30] Cera, J.; Henning, G.; Grossmann, I., 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 (1997)
[31] Mendez, C.; Cerda, J., Optimal scheduling of batch plants satisfying multiple product orders with different due-dates, Computers & Chemical Engineering, 24, 2223-2245 (2000)
[32] Yuan, J.; Xue, Y.; Hu, K.; Wu, H.; Jia, Q., On-line application oriented optimal scheduling for penicillin fed-batch fermentation, Chemical Engineering & Processing, 48, 651-658 (2009)
[33] Samsatli, N.; Shah, N., An optimization based design procedure for biochemical processes. Part II: detailed scheduling, Food and Bioproducts Processing: Transactions of the Institution of Chemical Engineers, Part C, 74, 4, 232-242 (1996)
[34] Crawley, M., Statistics: an introduction using R (2005), John Wiley & Sons: John Wiley & Sons Chichester, UK · Zbl 1080.62001
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.