Solving the nuclear dismantling project scheduling problem by combining mixed-integer and constraint programming techniques and metaheuristics

Journal of Scheduling - 2021
Felix Hübner1, Patrick Gerhards2, Christian Stürck3, Rebekka Volk1
1Institute for Industrial Production (IIP), Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany
2Institute of Computer Science, Helmut Schmidt University, Hamburg, Germany
3Institute for Management Science and Operations Research, Helmut Schmidt University, Hamburg, Germany

Tóm tắt

AbstractScheduling of megaprojects is very challenging because of typical characteristics, such as expected long project durations, many activities with multiple modes, scarce resources, and investment decisions. Furthermore, each megaproject has additional specific characteristics to be considered. Since the number of nuclear dismantling projects is expected to increase considerably worldwide in the coming decades, we use this type of megaproject as an application case in this paper. Therefore, we consider the specific characteristics of constrained renewable and non-renewable resources, multiple modes, precedence relations with and without no-wait condition, and a cost minimisation objective. To reliably plan at minimum costs considering all relevant characteristics, scheduling methods can be applied. But the extensive literature review conducted did not reveal a scheduling method considering the special characteristics of nuclear dismantling projects. Consequently, we introduce a novel scheduling problem referred to as the nuclear dismantling project scheduling problem. Furthermore, we developed and implemented an effective metaheuristic to obtain feasible schedules for projects with about 300 activities. We tested our approach with real-life data of three different nuclear dismantling projects in Germany. On average, it took less than a second to find an initial feasible solution for our samples. This solution could be further improved using metaheuristic procedures and exact optimisation techniques such as mixed-integer programming and constraint programming. The computational study shows that utilising exact optimisation techniques is beneficial compared to standard metaheuristics. The main result is the development of an initial solution finding procedure and an adaptive large neighbourhood search with iterative destroy and recreate operations that is competitive with state-of-the-art methods of related problems. The described problem and findings can be transferred to other megaprojects.

Từ khóa


Tài liệu tham khảo

Afshar, M. R., Shahhosseini, V., & Sebt, M. H. (2019). A genetic algorithm with a new local search method for solving the multimode resource-constrained project scheduling problem. International Journal of Construction Management, pp. 1–9

Alba, E., & Chicano, J. F. (2007). Software project management with GAs. Information Sciences, 177(11), 2380–2401.

Bartels, J. -H. (2009). Anwendung von Methoden der ressourcenbeschränkten Projektplanung mit multiplen Ausführungsmodi in der betriebswirtschaftlichen Praxis: Rückbauplanung für Kernkraftwerke und Versuchsträgerplanung in Automobilentwicklungsprojekten (Application of methods of resource-constrained project scheduling with multiple execution modes in the business-management practice: Dismantling planning for nuclear power plants and experimental vehicle planning in automotive development projects). Gabler Edition Wissenschaft : Produktion und Logistik. Gabler, Wiesbaden.

Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010). F-race and iterated f-race: An overview. In T. Bartz-Beielstein, M. Chiarandini, L. Paquete, & M. Preuss (Eds.), Experimental Methods for the Analysis of Optimization Algorithms (pp. 311–336). Berlin: Springer. 978-3-642-02537-2.

Brusa, L., DeSantis, R., Nurden, P. L., Walkden, P., Watson, B. (2002). The decommissioning of the trino nuclear power plant, URL https://www.osti.gov/servlets/purl/829556-bgfnku/native/. Waste Management 2002 Symposium, Tucson, AZ (US), 02/24/2002–02/28/2002.

Christodoulou, S. E., Michaelidou-Kamenou, A., & Ellinas, G. (2015). Heuristic methods for resource leveling problems. In C. Schwindt & J. Zimmermann (Eds.), Handbook on project management and scheduling (Vol. 1, pp. 389–407). Cham: Springer.

De Reyck, B., & Herroelen, W. (1998). A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. European Journal of Operational Research, 111(1), 152–174. https://doi.org/10.1016/S0377-2217(97)00305-6.

European Commission. (2016a). Nuclear illustrative programme: presented under article 40 of the euratom treaty for the opinion of the european economic and social committee, Retrieved November 19, 2018 URL https://ec.europa.eu/transparency/regdoc/rep/1/2016/EN/1-2016-177-EN-F1-1.PDF.

European Commission. (2016b), Nuclear Illustrative Programme presented under Article 40 of the Euratom Treaty for the opinion of the European Economic and Social Committee: Accompanying the document, Retrieved November 19, 2018 URL https://ec.europa.eu/energy/sites/ener/files/documents/1_EN_autre_document_travail_service_part1_v10.pdf.

Flyvbjerg, B. (2014). What you should know about megaprojects and why: An overview. Project Management Journal, 45(2), 6–19. https://doi.org/10.1002/pmj.21409.

Geiger, M. J. (2017). A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem. European Journal of Operational Research, 256(3), 729–741. https://doi.org/10.1016/j.ejor.2016.07.024.

Gerhards, P., Stürck, C., & Fink, A. (2017). An adaptive large neighborhood search as a matheuristic for the multi-mode resource-constrained project scheduling problem. European Journal of Industrial Engineering, 11(6), 774–791. https://doi.org/10.1504/EJIE.2017.10006713.

Herroelen, W., & Leus, R. (2005). Project scheduling under uncertainty: Survey and research potentials. European Journal of Operational Research, 165(2), 289–306. https://doi.org/10.1016/j.ejor.2004.04.002.

Hsu, C.-C., & Kim, D. S. (2005). A new heuristic for the multi-mode resource investment problem. Journal of the Operational Research Society, 56(4), 406–413. https://doi.org/10.1057/palgrave.jors.2601827.

IEA (2014). World Energy Outlook 2014. International Energy Agency, Paris, ISBN 978-92-64-20805-6.

Iguchi, Y., Kanehira, Y., Tachibana, M., & Johnsen, T. (2004). Development of Decommissioning Engineering Support System (DEXUS) of the Fugen Nuclear Power Station. Journal of Nuclear Science and Technology, 41(3), 367–375. https://doi.org/10.1080/18811248.2004.9715497.

Józefowska, J., Mika, M., Różycki, R., Waligóra, G., & Weglarz, J. (2001). Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102(1–4), 137–155.

Kelley, J. E. (1963). The critical-path method: Resources planning and scheduling. Industrial Scheduling, 13(1), 347–365.

Klasen, J., & Seizer, B. (2015). Managing complexity of nuclear decommissioning & dismantling projects—an advanced project-management approach, ICOND conference, 18.11.2015, Bonn.

Kolisch, R. (1996). Efficient priority rules for the resource-constrained project scheduling problem. Journal of Operations Management, 14(3), 179–192.

Kreter, S., Schutt, A., Stuckey, P. J., & Zimmermann, J. (2018). Mixed-integer linear programming and constraint programming formulations for solving resource availability cost problems. European Journal of Operational Research, 266(2), 472–486. https://doi.org/10.1016/j.ejor.2017.10.014.

Laborie, P., Rogerie, J., Shaw, P., & Vilím, P. (2018). IBM ILOG CP optimizer for scheduling. Constraints, 23(2), 210–250.

López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58.

Martí, R., Resende, M. G., & Ribeiro, C. C. (2013). Multi-start methods for combinatorial optimization. European Journal of Operational Research, 226(1), 1–8. https://doi.org/10.1016/j.ejor.2012.10.012.

Mika, M., Waligóra, G., & Weglarz, J. (2015). Overview and state of the art. In C. Schwindt & J. Zimmermann (Eds.), Handbook on Project Management and Scheduling (Vol. 1, pp. 445–490). Cham: Springer.

Möhring, R. H. (1984). Minimizing costs of resource requirements in project networks subject to a fixed completion time. Operations Research, 32(1), 89–120. https://doi.org/10.1287/opre.32.1.89.

Muller, L. F. (2011). An adaptive large neighborhood search algorithm for the multi-mode RCPSP. Technical report, Report 3.2011, Department of Management Engineering, Technical University of Denmark,

NEA. (2016). Costs of decommissioning nuclear power plants. Paris: OECD Publishing.

Neumann, K., Schwindt, C., & Zimmermann, J. (2003). Project scheduling with time windows and scarce resources: Temporal and resource-constrained project scheduling with regular and nonregular objective functions. Berlin: Springer.

Rieck, J., & Zimmermann, J. (2015). Exact methods for resource leveling problems. In C. Schwindt & J. Zimmermann (Eds.), Handbook on project management and scheduling (Vol. 1, pp. 361–387). Cham: Springer.

Rodrigues, S. B., & Yamashita, D. S. (2015). Exact methods for the resource availability cost problem. In C. Schwindt & J. Zimmermann (Eds.), Handbook on project management and scheduling (Vol. 1, pp. 319–338). Cham: Springer.

Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135.

Schnell, A., & Hartl, R. F. (2016). On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations. OR Spectrum, 38(2), 283–303. https://doi.org/10.1007/s00291-015-0419-6.

Schnell, A., & Hartl, R. F. (2017). On the generalization of constraint programming and boolean satisfiability solving techniques to schedule a resource-constrained project consisting of multi-mode jobs. Operations Research Perspectives, 4(1), 1–11. https://doi.org/10.1016/j.orp.2017.01.002.

Shadrokh, S., & Kianfar, F. (2007). A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research, 181(1), 86–101. https://doi.org/10.1016/j.ejor.2006.03.056.

Shaw, P. (1997). A new local search algorithm providing high quality solutions to vehicle routing problems. Glasgow, Scotland: APES Group: Department of Computer Science, University of Strathclyde Glasgow, Scotland, UK.

Talbot, F. B. (1982). Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 28(10), 1197–1210. https://doi.org/10.1287/mnsc.28.10.1197.

Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.

Tormos, P., & Lova, A. (2001). A competitive heuristic solution technique for resource-constrained project scheduling. Annals of Operations Research, 102(1–4), 65–81.

van Peteghem, V., & Vanhoucke, M. (2014). An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, 235(1), 62–72. https://doi.org/10.1016/j.ejor.2013.10.012.

van Peteghem, V., & Vanhoucke, M. (2015). Heuristic methods for the resource availability cost problem. In J. Zimmermann & C. Schwindt (Eds.), Handbook on project management and scheduling (Vol. 1, pp. 339–359). Cham: Springer. ISBN 978-3-319-05443-8.

Vega-Velázquez, M. Á., García-Nájera, A., & Cervantes, H. (2018). A survey on the software project scheduling problem. International Journal of Production Economics, 202, 145–161.

Volk, R., Hübner, F., Hünlich, T., & Schultmann, F. (2019). The future of nuclear decommissioning—a worldwide market potential study. Energy Policy, 124, 226–261. https://doi.org/10.1016/j.enpol.2018.08.014.

WNA. (2017) Decommissioning nuclear facilities, Retrieved November 19, 2018. URL http://world-nuclear.org/information-library/nuclear-fuel-cycle/nuclear-wastes/decommissioning-nuclear-facilities.aspx.

Yanagihara, S., Sukegawa, T., & Shiraishi, K. (2012). Development of computer systems for planning and management of reactor decommissioning. Journal of Nuclear Science and Technology, 38(3), 193–202. https://doi.org/10.1080/18811248.2001.9715021.

Zhu, X., Ruiz, R., Li, S., & Li, X. (2017). An effective heuristic for project scheduling with resource availability cost. European Journal of Operational Research, 257(3), 746–762. https://doi.org/10.1016/j.ejor.2016.08.049.

Thông tin
Thông tin xuất bản

Journal of Scheduling

Thông tin tác giả