An efficient MILP-based decomposition strategy for solving large-scale scheduling problems in the shipbuilding industry. (English) Zbl 1439.90070
Summary: This work presents a novel hybrid and systematic MILP-based solution approach for the resolution of multi-stage scheduling problems arising in the shipbuilding industry. The manufacturing problem involves the processing of a large number of sub-blocks and blocks, which should be rigorously produced and assembled with the aim of finalizing a project on time. Firstly, this paper presents three alternative rigorous MILP mathematical formulations relied on a continuous-time representation for solving the problem under study. Although the objective values reported by these exact optimization approaches outperform the results found through other solution techniques proposed in the literature to solve the same problem instances, the main drawback of the MILP models is the high computation time. Therefore, this work proposes an algorithm for solving the mathematical models in a decomposable way with the goal of accelerating the resolution times. The applicability of our proposal is demonstrated by effectively coping with several instances of a real-world case study dealing with the construction of a ship for the development of marine resources. Computational results show that the proposed decomposition method is able to obtain high-quality solutions in few seconds of CPU time for all examples considered.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aguirre AM, Méndez CA, Gutierrez G, De Prada C (2012) An improvement-based MILP optimization approach to complex AWS scheduling. Comput Chem Eng 47:217-226. https://doi.org/10.1016/j.compchemeng.2012.06.036 · doi:10.1016/j.compchemeng.2012.06.036 |
| [2] | Basán NP, Achkar VG, Méndez CA, Garcia-del-valle A (2017) A heuristic simulation-based framework to improve the scheduling of blocks assembly and the production process in shipbuilding. Winter Simul Conf WSC F134102:3218-3229. https://doi.org/10.1109/WSC.2017.8248040 · doi:10.1109/WSC.2017.8248040 |
| [3] | Basán NP, Achkar VG, Garcia-del-valle A, Méndez CA (2018) An effective continuous-time formulation for scheduling optimization in a shipbuilding. Iberoam J Ind Eng 10:34-48 |
| [4] | Castro PM, Harjunkoski I, Grossmann IE (2009) New continuous-time scheduling formulation for continuous plants under variable electricity cost. Ind Eng Chem Res 48:6701-6714. https://doi.org/10.1021/ie900073k · doi:10.1021/ie900073k |
| [5] | Cebral-Fernandez M, Crespo-Pereira D, Garcia-Del-Valle A, Rouco-Couzo M (2016) Improving planning and resource utilization of a shipbuilding process based on simulation. In: 28th European Modeling and Simulation Symposium, EMSS 2016, pp 197-203 |
| [6] | Cerdá J, Henning GP, Grossmann IE (1997) A Mixed-integer linear programming model for short-term scheduling of single-stage multiproduct batch plants with parallel lines. Ind Eng Chem Res 36:1695-1707. https://doi.org/10.1021/ie9605490 · doi:10.1021/ie9605490 |
| [7] | Cho KK, Oh SJ, Ryu KR, Choi HR (1998) An integrated process planning and scheduling system for block assembly in shipbuilding. CIRP Ann Manuf Technol 47:419-422 · doi:10.1016/S0007-8506(07)62865-0 |
| [8] | Chu Y, You F, Wassick JM (2014) Hybrid agent-based method for scheduling of complex batch processes. Comput Chem Eng 60:277-296. https://doi.org/10.1109/ACC.2014.6858592 · doi:10.1109/ACC.2014.6858592 |
| [9] | Cóccola ME, Cafaro VG, Méndez CA, Cafaro DC (2014) Enhancing the general precedence approach for industrial scheduling problems with sequence-dependent issues. Ind Eng Chem Res 53:17092-17097. https://doi.org/10.1021/ie500803p · doi:10.1021/ie500803p |
| [10] | Cóccola ME, Dondo R, Méndez CA (2015) A MILP-based column generation strategy for managing large-scale maritime distribution problems. Comput Chem Eng 72:350-362. https://doi.org/10.1016/j.compchemeng.2014.04.008 · doi:10.1016/j.compchemeng.2014.04.008 |
| [11] | Fettaka S, Thibault J, Gupta Y (2015) A new algorithm using front prediction and NSGA-II for solving two and three-objective optimization problems. Optim Eng 16:713-736. https://doi.org/10.1007/s11081-014-9271-9 · Zbl 1364.90300 · doi:10.1007/s11081-014-9271-9 |
| [12] | Hasebe S, Hashimoto I, Ishikawa A (1991) General reordering algorithm for scheduling of batch processes. J Chem Eng Jpn 24:483-489. https://doi.org/10.1252/jcej.24.483 · doi:10.1252/jcej.24.483 |
| [13] | Kim H, Kang J, Park S (2002) Scheduling of shipyard block assembly process using constraint satisfaction problem scheduling of shipyard block assembly process using constraint satisfaction problem. Asia Pac Manag Rev 7:119-138 |
| [14] | Koh S, Eom C, Jang J, Choi Y (2008) An improved spatial scheduling algorithm for block assembly shop in shipbuilding company. In: 2008 3rd international conference on innovative computing information and control. IEEE, pp 253-253 |
| [15] | Kopanos GM, Laínez JM, Puigjaner L (2009) An efficient mixed-integer linear programming scheduling framework for addressing sequence-dependent setup issues in batch plants. Ind Eng Chem Res 48:6346-6357. https://doi.org/10.1021/ie801127t · doi:10.1021/ie801127t |
| [16] | Kopanos GM, Méndez CA, Puigjaner L (2010) MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: a benchmark scheduling problem of the pharmaceutical industry. Eur J Oper Res 207:644-655. https://doi.org/10.1016/j.ejor.2010.06.002 · Zbl 1205.90126 · doi:10.1016/j.ejor.2010.06.002 |
| [17] | Larson J, Wild SM (2016) A batch, derivative-free algorithm for finding multiple local minima. Optim Eng 17:205-228. https://doi.org/10.1007/s11081-015-9289-7 · Zbl 1364.90363 · doi:10.1007/s11081-015-9289-7 |
| [18] | Lee K, Shin JG, Ryu C (2009) Development of simulation-based production execution system in a shipyard: a case study for a panel block assembly shop. Prod Plan Control 20:750-768. https://doi.org/10.1080/09537280903164128 · doi:10.1080/09537280903164128 |
| [19] | Maravelias CT, Sung C (2009) Integration of production planning and scheduling: overview, challenges and opportunities. Comput Chem Eng 33:1919-1930. https://doi.org/10.1016/j.compchemeng.2009.06.007 · doi:10.1016/j.compchemeng.2009.06.007 |
| [20] | Méndez CA, Cerdá J (2003a) Dynamic scheduling in multiproduct batch plants. Comput Chem Eng 27:1247-1259. https://doi.org/10.1016/S0098-1354(03)00050-4 · doi:10.1016/S0098-1354(03)00050-4 |
| [21] | Méndez CA, Cerdá J (2003b) An MILP continuous-time framework for short-term scheduling of multipurpose batch processes under different operation strategies. Optim Eng 4:7-22. https://doi.org/10.1023/A:1021856229236 · Zbl 1046.90052 · doi:10.1023/A:1021856229236 |
| [22] | Méndez C, Henning G, Cerdá J (2000) Optimal scheduling of batch plants satisfying multiple product orders with different due-dates. Comput Chem Eng 24:2223-2245. https://doi.org/10.1016/S0098-1354(00)00584-6 · doi:10.1016/S0098-1354(00)00584-6 |
| [23] | Méndez CA, Henning GP, Cerdá J (2001) An MILP continuous-time approach to short-term scheduling of resource-constrained multistage flowshop batch facilities. Comput Chem Eng 25:701-711. https://doi.org/10.1016/S0098-1354(01)00671-8 · doi:10.1016/S0098-1354(01)00671-8 |
| [24] | Méndez CA, Cerdá J, Grossmann IE et al (2006) State-of-the-art review of optimization methods for short-term scheduling of batch processes. Comput Chem Eng 30:913-946. https://doi.org/10.1016/j.compchemeng.2006.02.008 · doi:10.1016/j.compchemeng.2006.02.008 |
| [25] | Persson JA, Ölvander J (2015) Optimization of the complex-RFM optimization algorithm. Optim Eng 16:27-48. https://doi.org/10.1007/s11081-014-9247-9 · Zbl 1364.90414 · doi:10.1007/s11081-014-9247-9 |
| [26] | Pinto JM, Grossmann IE (1995) A continuous time mixed integer linear programming model for short term scheduling of multistage batch plants. Ind Eng Chem Res 34:3037-3051. https://doi.org/10.1021/ie00048a015 · doi:10.1021/ie00048a015 |
| [27] | Roslöf J, Harjunkoski I, Westerlund T, Isaksson J (1999) A short-term scheduling problem in the paper-converting industry. Comput Chem Eng 23:S871-S874. https://doi.org/10.1016/S0098-1354(99)80214-2 · doi:10.1016/S0098-1354(99)80214-2 |
| [28] | Roslöf J, Harjunkoski I, Björkqvist J et al (2001) An MILP-based reordering algorithm for complex industrial scheduling and rescheduling. Comput Chem Eng 25:821-828. https://doi.org/10.1016/S0098-1354(01)00674-3 · doi:10.1016/S0098-1354(01)00674-3 |
| [29] | Roslöf J, Harjunkoski I, Westerlund T, Isaksson J (2002) Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure. Eur J Oper Res 138:29-42. https://doi.org/10.1016/S0377-2217(01)00140-0 · Zbl 1008.90024 · doi:10.1016/S0377-2217(01)00140-0 |
| [30] | Schweiger J, Liers F (2018) A decomposition approach for optimal gas network extension with a finite set of demand scenarios. Optim Eng 19:297-326. https://doi.org/10.1007/s11081-017-9371-4 · Zbl 1397.90085 · doi:10.1007/s11081-017-9371-4 |
| [31] | Seo Y, Sheen D, Kim T (2007) Block assembly planning in shipbuilding using case-based reasoning. Expert Syst Appl 32:245-253. https://doi.org/10.1016/j.eswa.2005.11.013 · doi:10.1016/j.eswa.2005.11.013 |
| [32] | Shang Z, Gu J, Ding W, Duodu EA (2017) Spatial scheduling optimization algorithm for block assembly in shipbuilding. Math Probl Eng 2017:1-10. https://doi.org/10.1155/2017/1923646 · Zbl 1426.90137 · doi:10.1155/2017/1923646 |
| [33] | Shin K, Ciccantell PS (2009) The steel and shipbuilding industries of south korea: rising east ASIA and globalization. Statew Agric Land Use Baseline XV:167-192. https://doi.org/10.1017/cbo9781107415324.004 · doi:10.1017/cbo9781107415324.004 |
| [34] | Tenne Y (2015) An adaptive-topology ensemble algorithm for engineering optimization problems. Optim Eng 16:303-334. https://doi.org/10.1007/s11081-014-9260-z · Zbl 1364.74085 · doi:10.1007/s11081-014-9260-z |
| [35] | Xiong F, Xing K, Wang F (2015) Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time. Eur J Oper Res 240:338-354. https://doi.org/10.1016/j.ejor.2014.07.004 · Zbl 1357.90061 · doi:10.1016/j.ejor.2014.07.004 |
| [36] | Zhuo L, Huat DCK, Wee KH (2012) Scheduling dynamic block assembly in shipbuilding through hybrid simulation and spatial optimisation. Int J Prod Res 50:5986-6004. https://doi.org/10.1080/00207543.2011.639816 · doi:10.1080/00207543.2011.639816 |
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.
