Large neighborhood search for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective. (English) Zbl 07897686
Summary: This paper deals with a scheduling problem arising at the tactical decision level in aeronautical assembly line. It has the structure of a challenging multi-mode resource-constrained project scheduling problem with incompatibility constraints, a resource leveling objective and also a large number of tasks. We first present a new event-based mixed-integer linear programming formulation and a standard constraint programming formulation of the problem. A large-neighborhood search approach based on the constraint programming model and tailored to the resource leveling objective is proposed. The approaches are tested and compared using industrial instances, yielding significant improvement compared to the heuristic currently used by the company. Moreover, the large-neighborhood search method significantly improves the method proposed in the literature on a related multi-mode resource investment problem when short CPU times are required.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B30 | Production models |
| 90C11 | Mixed integer programming |
| 90C05 | Linear programming |
Keywords:
aeronautical assembly line scheduling; multiple modes; resource leveling; mixed integer linear programming; constraint programming; large neighborhood searchReferences:
| [1] | Alvarez-Valdés, R.; Tamarit, J., The project scheduling polyhedron: Dimension, facets and lifting theorems, European Journal of Operational Research, 67, 204-220, 1993 · Zbl 0779.90036 · doi:10.1016/0377-2217(93)90062-R |
| [2] | Arkhipov, D., Battaïa, O., Cegarra, J., Lazarev, A. (2018). Operator assignment problem in aircraft assembly lines: A new planning approach taking into account economic and ergonomic constraints. In 7th CIRP conference on assembly technologies and systems (CATS 2018) (Vol. 76, pp. 63-66). |
| [3] | Artigues, C.; Demassey, S.; Néron, E., Resource-constrained project scheduling: Models, algorithms, extensions and applications, 2010, Wiley |
| [4] | Artigues, C., & Hébrard, E. (2013). MIP relaxation and large neighborhood search for a multi-mode resource-constrained multi-project scheduling problem. In 6th Multidisciplinary international conference on scheduling: Theory and applications (MISTA) (pp. 814-819). Ghent, Belgium. |
| [5] | Artigues, C.; Koné, O.; Lopez, P.; Mongeau, M.; Schwindt, C.; Zimmermann, J., Mixed-integer linear programming formulations, Handbook on project management and scheduling, 17-41, 2015, Springer · doi:10.1007/978-3-319-05443-8_2 |
| [6] | Artigues, C.; Michelon, P.; Reusser, S., Insertion techniques for static and dynamic resource-constrained project scheduling, European Journal of Operational Research, 149, 2, 249-267, 2003 · Zbl 1040.90013 · doi:10.1016/S0377-2217(02)00758-0 |
| [7] | Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling: Applying constraint programming to scheduling problems. Kluwer. · Zbl 1094.90002 |
| [8] | Biele, A.; Mönch, L., Hybrid approaches to optimize mixed-model assembly lines in low-volume manufacturing, Journal of Heuristics, 24, 1, 49-81, 2018 · doi:10.1007/s10732-017-9357-6 |
| [9] | Borreguero, T. (2020). Scheduling with limited resources along the aeronautical supply chain: From parts manufacturing plants to final assembly lines (Unpublished doctoral dissertation). Universidad Politécnica de Madrid. |
| [10] | Borreguero, T., Artigues, C., García Sánchez, A., Ortega Mier, M., Lopez, P. (2015a). Multimode time-constrained scheduling problems with generalized temporal constraints and labor skills. In 7th multidisciplinary international conference on scheduling: Theory and applications (MISTA) (pp. 809-813). Prague, Czech Republic. |
| [11] | Borreguero, T., García Sánchez, A., Ortega Mier, M. (2015b). Scheduling in the aeronautical industry using a mixed integer linear problem formulation. The Manufacturing Engineering Society International Conference, MESIC 2015 Procedia Engineering, 132 , 982-989. |
| [12] | Borreguero, T.; Mas, F.; Menéndez, J.; Barreda, M., Enhanced assembly line balancing and scheduling methodology for the aeronautical industry, Procedia Engineering, 132, 990-997, 2015 · doi:10.1016/j.proeng.2015.12.587 |
| [13] | Borreguero-Sanchidrián, T., García-Sánchez, Á., Ortega Mier, M. (2014). A MILP event based formulation for a real-world multimode RCSP with generalized temporal constraints. Managing complexity (pp. 113-120). Springer. |
| [14] | Bortolini, M., Calabrese, F., Galizia, F.G., Mora, C., Ventura, V. (2021). Industry 4.0 technologies: A cross-sector industry-based analysis. Proceedings of the international conference on sustainable design and manufacturing (pp. 140-148). |
| [15] | Boysen, N.; Schulze, P.; Scholl, A., Assembly line balancing: What happened in the last fifteen years?, European Journal of Operational Research, 301, 3, 797-814, 2022 · Zbl 1506.90087 · doi:10.1016/j.ejor.2021.11.043 |
| [16] | Brimberg, J.; Hurley, W.; Wright, R., Scheduling workers in a constricted area, Naval Research Logistics (NRL), 43, 1, 143-149, 1996 · Zbl 0863.90083 · doi:10.1002/(SICI)1520-6750(199602)43:1<143::AID-NAV9>3.0.CO;2-B |
| [17] | Brucker, P.; Knust, S., Complex scheduling, 2011, Springer |
| [18] | Buergin, J.; Helming, S.; Andreas, J.; Blaettchen, P.; Schweizer, Y.; Bitte, F.; Lanza, G., Local order scheduling for mixed-model assembly lines in the aircraft manufacturing industry, Production Engineering, 12, 759-767, 2018 · doi:10.1007/s11740-018-0852-x |
| [19] | Coelho, J.; Vanhoucke, M., Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers, European Journal of Operational Research, 213, 1, 73-82, 2011 · Zbl 1237.90086 · doi:10.1016/j.ejor.2011.03.019 |
| [20] | Cordeau, J-F; Laporte, G.; Pasin, F.; Ropke, S., Scheduling technicians and tasks in a telecommunications company, Journal of Scheduling, 13, 4, 393-409, 2010 · Zbl 1231.90258 · doi:10.1007/s10951-010-0188-7 |
| [21] | Coughlan, ET; Lübbecke, ME; Schulz, J., A branch-price-andcut algorithm for multi-mode resource leveling, European Journal of Operational Research, 245, 1, 70-80, 2015 · Zbl 1346.90335 · doi:10.1016/j.ejor.2015.02.043 |
| [22] | De Reyck, B.; Herroelen, W., The multi-mode resource-constrained project scheduling problem with generalized precedence relations, European Journal of Operational Research, 119, 2, 538-556, 1999 · Zbl 0934.90040 · doi:10.1016/S0377-2217(99)00151-4 |
| [23] | Demeulemeester, E., Minimizing resource availability costs in timelimited project networks, Management Science, 41, 10, 1590-1598, 1995 · Zbl 0861.90071 · doi:10.1287/mnsc.41.10.1590 |
| [24] | Demeulemeester, E.; Herroelen, W., Project scheduling: A research handbook. international series in operations research & management science, 2002, Springer · Zbl 1059.90068 |
| [25] | Drexl, A.; Gruenewald, J., Non-preemptive multi-mode resourceconstrained project scheduling, IIE Transactions, 25, 5, 74-81, 1993 · doi:10.1080/07408179308964317 |
| [26] | Gerhards, P., The multi-mode resource investment problem: A benchmark library and a computational study of lower and upper bounds, OR Spectrum, 42, 4, 901-933, 2020 · Zbl 1454.90018 · doi:10.1007/s00291-020-00595-9 |
| [27] | Godard, D., Laborie, P., Nuijten, W. (2005). Randomized large neighborhood search for cumulative scheduling. ICAPS (Vol. 5, pp. 81-89). |
| [28] | Hartmann, S.; Briskorn, D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207, 1, 1-14, 2010 · Zbl 1205.90123 · doi:10.1016/j.ejor.2009.11.005 |
| [29] | Hemmelmayr, VC; Cordeau, J-F; Crainic, TG, An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics, Computers & Operations Research, 39, 12, 3215-3228, 2012 · Zbl 1349.90858 · doi:10.1016/j.cor.2012.04.007 |
| [30] | Kagermann, H., & Wahlster, W. (2013). Recommendations for implementing the strategic initiative Industry 4.0: Securing the future of german manufacturing industry. Final report of the Industry 4.0 Working Group. |
| [31] | Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation, European Journal of Operational Research, 90, 2, 320-333, 1996 · Zbl 0916.90151 · doi:10.1016/0377-2217(95)00357-6 |
| [32] | Kolisch, R., Make-to-order assembly management, 2000, Springer · Zbl 0945.90513 |
| [33] | Koné, O.; Artigues, C.; Lopez, P.; Mongeau, M., Event-based MILP models for resource-constrained project scheduling problems, Computers & Operations Research, 38, 1, 3-13, 2011 · Zbl 1231.90202 · doi:10.1016/j.cor.2009.12.011 |
| [34] | Kreter, S.; Schutt, A.; Stuckey, PJ, Using constraint programming for solving RCPSP/max-cal, Constraints, 22, 3, 432-462, 2017 · Zbl 1387.90092 · doi:10.1007/s10601-016-9266-6 |
| [35] | Laborie, P., & Godard, D. (2007). Self-adapting large neighborhood search: Application to single-mode scheduling problems. (Vol. 8). Paris. |
| [36] | Laborie, P.; Rogerie, J.; Shaw, P.; Vilím, P., IBM ILOG CP Optimizer for scheduling, Constraints, 23, 2, 210-250, 2018 · Zbl 1400.90169 · doi:10.1007/s10601-018-9281-x |
| [37] | Maenhout, B.; Vanhoucke, M., An integrated nurse staffing and scheduling analysis for longer-term nursing staff allocation problems, Omega, 41, 2, 485-499, 2013 · doi:10.1016/j.omega.2012.01.002 |
| [38] | Mas, F.; Arista, R.; Oliva, M.; Hiebert, B.; Gilkerson, I.; Ríos, J., A review of PLM impact on US and EU aerospace industry, Procedia Engineering, 132, 1053-1060, 2015 · doi:10.1016/j.proeng.2015.12.595 |
| [39] | Mas, F., Menéndez, J.L., Oliva, M., Servan, J., Arista, R., Del Valle, C. (2014). Design within complex environments: Collaborative engineering in the aerospace industry. Information system development (pp. 197-205). Springer. |
| [40] | Mas, F.; Ríos, J.; Gómez, A.; Hernández, JC, Knowledge-based application to define aircraft final assembly lines at the industrialisation conceptual design phase, International Journal of Computer Integrated Manufacturing, 29, 6, 677-691, 2016 · doi:10.1080/0951192X.2015.1068453 |
| [41] | Nouri, N., Krichen, S., Ladhari, T., Fatimah, P. (2013). A discrete artificial bee colony algorithm for resource-constrained project scheduling problem. In 5th international conference on modeling, simulation and applied optimization (ICMSAO 2013) (p. 1-6). |
| [42] | Palpant, M.; Artigues, C.; Michelon, P., LSSPER: Solving the resource constrained project scheduling problem with large neighbourhood search, Annals of Operations Research, 131, 1-4, 237-257, 2004 · Zbl 1066.90037 · doi:10.1023/B:ANOR.0000039521.26237.62 |
| [43] | Polo Mejía, O.; Artigues, C.; Lopez, P.; Basini, V., Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility, International Journal of Production Research, 58, 23, 7149-7166, 2020 · doi:10.1080/00207543.2019.1693654 |
| [44] | Pritsker, AAB; Watters, LJ; Wolfe, PM, Multiproject scheduling with limited resources: A zero-one programming approach, Management Science, 16, 1, 93-108, 1969 · doi:10.1287/mnsc.16.1.93 |
| [45] | Schwindt, C.; Zimmermann, J., Handbook on project management and scheduling, 2015, Springer · doi:10.1007/978-3-319-05443-8 |
| [46] | Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. M.J. Maher & J.-F. Puget (Eds.), In Principles and practice of constraint programming - CP’98, 4th international conference(Vol. 1520, pp. 417-431). Pisa, Italy: Springer. |
| [47] | Thomas, C., & Schaus, P. (2018). Revisiting the self-adaptive large neighborhood search. In International conference on the integration of constraint programming, artificial intelligence, and operations research (pp. 557-566). · Zbl 1508.68350 |
| [48] | Wang, H.; Li, T.; Lin, D., Efficient genetic algorithm for resource constrained project scheduling problem, Transactions of Tianjin University, 16, 5, 376-382, 2010 · doi:10.1007/s12209-010-1495-y |
| [49] | Weglarz, J.; Józefowska, J.; Mika, M.; Waligóra, G., Project scheduling with finite or infinite number of activity processing modes - A survey, European Journal of Operational Research, 208, 3, 177-205, 2011 · Zbl 1208.90082 · doi:10.1016/j.ejor.2010.03.037 |
| [50] | Young, K.D., Feydy, T., Schutt, A. (2017). Constraint programming applied to the multi-skill project scheduling problem. Principles and practice of constraint programming: 23rd international conference (CP 2017) (pp. 308-317). Melbourne, VIC, Australia. |
| [51] | Zapata, J.; Hodge, B.; Reklaitis, G., The multimode resource constrained multiproject scheduling problem: Alternative formulations, AIChE Journal, 54, 8, 2101-2119, 2008 · doi:10.1002/aic.11522 |
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.
