×

A local search framework for industrial test laboratory scheduling. (English) Zbl 1476.90129

Summary: In this paper we introduce a complex scheduling problem that arises in a real-world industrial test laboratory, where a large number of activities has to be performed using qualified personnel and specialized equipment, subject to time windows and several other constraints. The problem is an extension of the well-known Resource-Constrained Project Scheduling Problem and features multiple heterogeneous resources with very general availability restrictions, as well as a grouping phase, where the jobs have to be assembled from smaller units. We describe an instance generator for this problem and publicly available instance sets, both randomly generated and real-world data. Finally, we present and evaluate different metaheuristic approaches to solve the scheduling subproblem, where the assembled jobs are already provided. Our results show that Simulated Annealing can be used to achieve very good results, in particular for large instances, where it is able to consistently find better solutions than a state-of-the-art constraint programming solver within reasonable time.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

CHUFFED; SMAC; MiniZinc
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmeti, A., & Musliu, N. (2018). Min-conflicts heuristic for multi-mode resource-constrained projects scheduling. In: Proceedings of the Genetic and Evolutionary Computation Conference, ACM, pp 237-244
[2] Asta, S.; Karapetyan, D.; Kheiri, A.; Özcan, E.; Parkes, AJ, Combining monte-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem, Information Sciences, 373, 476-498 (2016) · doi:10.1016/j.ins.2016.09.010
[3] Bartels, JH; Zimmermann, J., Scheduling tests in automotive r&d projects, European Journal of Operational Research, 193, 3, 805-819 (2009) · Zbl 1179.90123 · doi:10.1016/j.ejor.2007.11.010
[4] Bellenguez, O.; Néron, E.; Trick, M.; Burke, E., Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills, Practice and Theory of Automated Timetabling V, 229-243 (2005), Berlin: Springer Berlin Heidelberg, Berlin · doi:10.1007/11593577_14
[5] Blazewicz, J.; Lenstra, JK; Kan, AR, Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5, 1, 11-24 (1983) · Zbl 0516.68037 · doi:10.1016/0166-218X(83)90012-4
[6] Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research 149(2):268 - 281, doi:10.1016/S0377-2217(02)00761-0, http://www.sciencedirect.com/science/article/pii/S0377221702007610, sequencing and Scheduling · Zbl 1040.90015
[7] Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research, 112, 1, 3-41 (1999) · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5
[8] Chu G (2011) Improving combinatorial optimization. PhD thesis, University of Melbourne, Australia, http://hdl.handle.net/11343/36679
[9] Dauzère-Pérès, S.; Roux, W.; Lasserre, J., Multi-resource shop scheduling with resource flexibility, European Journal of Operational Research, 107, 2, 289-305 (1998) · Zbl 0943.90028 · doi:10.1016/S0377-2217(97)00341-X
[10] Drexl, A.; Nissen, R.; Patterson, JH; Salewski, F., Progen/\( \pi\) x -an instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions, European Journal of Operational Research, 125, 1, 59-72 (2000) · Zbl 0972.90029 · doi:10.1016/S0377-2217(99)00205-2
[11] Elmaghraby, SE, Activity networks: Project planning and control by network models (1977), New Jersey: Wiley, New Jersey · Zbl 0385.90076
[12] Geibinger T, Mischek F, Musliu N (2019) Investigating constraint programming for real world industrial test laboratory scheduling. In: Proceedings of the Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019) · Zbl 1525.90200
[13] Gonçalves, J.; Mendes, J.; Resende, M., A genetic algorithm for the resource constrained multi-project scheduling problem, European Journal of Operational Research, 189, 3, 1171-1190 (2008) · Zbl 1146.90412 · doi:10.1016/j.ejor.2006.06.074
[14] Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics (NRL), 45, 7, 733-750 (1998) · Zbl 0936.90024 · doi:10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C
[15] 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
[16] Hutter F, Hoos HH, Leyton-Brown K (2011) Sequential model-based optimization for general algorithm configuration. In: International Conference on Learning and Intelligent Optimization, Springer, pp 507-523
[17] Kirkpatrick, S.; Gelatt, CD; Vecchi, MP, Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[18] Laurent, A.; Deroussi, L.; Grangeon, N.; Norre, S., A new extension of the rcpsp in a multi-site context: Mathematical model and metaheuristics, Computers and Industrial Engineering, 112, 634-644 (2017) · doi:10.1016/j.cie.2017.07.028
[19] Mika, M.; Waligóra, G.; Wȩglarz, J., Modelling setup times in project scheduling. Perspectives in modern project scheduling, 131-163 (2006), Boston: Springer, Boston · Zbl 1127.90033
[20] Mika, M.; Waligóra, G.; Wȩglarz, J.; Schwindt, C.; Zimmermann, J., Overview and state of the art, Handbook on Project Management and Scheduling, 445-490 (2015), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-319-05443-8_21
[21] Minton, S.; Johnston, MD; Philips, AB; Laird, P., Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, 58, 161-205 (1992) · Zbl 0782.90054 · doi:10.1016/0004-3702(92)90007-K
[22] Mischek F, Musliu N (2018) The test laboratory scheduling problem. Technical report, Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, TU Wien, CD-TR 2018/1
[23] Nethercote N, Stuckey PJ, Becket R, Brand S, Duck GJ, Tack G (2007) Minizinc: Towards a standard CP modelling language. In: Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, pp 529-543, doi:10.1007/978-3-540-74970-7_38
[24] Pellerin, R.; Perrier, N.; Berthaut, F., A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, European Journal of Operational Research, 280, 2, 395-416 (2020) · Zbl 1430.90286 · doi:10.1016/j.ejor.2019.01.063
[25] Polo Mejia O, Anselmet MC, Artigues C, Lopez P (2017) A new RCPSP variant for scheduling research activities in a nuclear laboratory. In: 47th International Conference on Computers & Industrial Engineering (CIE47), Lisbonne, Portugal, p 8p., https://hal.laas.fr/hal-01630977
[26] Potts, CN; Kovalyov, MY, Scheduling with batching: A review, European Journal of Operational Research, 120, 2, 228-249 (2000) · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8
[27] Salewski, F.; Schirmer, A.; Drexl, A., Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application, European Journal of Operational Research, 102, 1, 88-110 (1997) · Zbl 0948.90060 · doi:10.1016/S0377-2217(96)00219-6
[28] Schwindt, C.; Trautmann, N., Batch scheduling in process industries: An application of resource-constrained project scheduling, OR-Spektrum, 22, 4, 501-524 (2000) · Zbl 0985.90042 · doi:10.1007/s002910000042
[29] Szeredi R, Schutt A (2016) Modelling and solving multi-mode resource-constrained project scheduling. In: Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings, pp 483-492, doi:10.1007/978-3-319-44953-1_31
[30] Trautmann, N.; Schwindt, C., A minlp/rcpsp decomposition approach for the short-term planning of batch production. In: computer aided chemical engineering, 1309-1314 (2005), Amsterdam: Elsevier, Amsterdam
[31] Villafáñez, F.; Poza, D.; López-Paredes, A.; Pajares, J.; del Olmo, R., A generic heuristic for multi-project scheduling problems with global and local resource constraints (rcmpsp), Soft Computing, 23, 10, 3465-3479 (2019) · doi:10.1007/s00500-017-3003-y
[32] Wauters, T.; Kinable, J.; Smet, P.; Vancroonenburg, W.; Vanden Berghe, G.; Verstichel, J., The multi-mode resource-constrained multi-project scheduling problem, Journal of Scheduling, 19, 3, 271-283 (2016) · Zbl 1347.90052 · doi:10.1007/s10951-014-0402-0
[33] Wȩglarz, 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
[34] Wilson M, Witteveen C, Huisman B (2012) Enhancing predictability of schedules by task grouping. In: BNAIC 2012: 24th Benelux Conference on Artificial Intelligence, Maastricht, The Netherlands, 25-26 October 2012, Citeseer
[35] Young, KD; Feydy, T.; Schutt, A.; Beck, JC, Constraint programming applied to the multi-skill project scheduling problem, Principles and Practice of Constraint Programming, 308-317 (2017), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-319-66158-2_20
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.