A data-driven meta-learning recommendation model for multi-mode resource constrained project scheduling problem. (English) Zbl 1542.90091
Summary: Meta-heuristics widely proposed in addressing multi-mode resource constrained project scheduling problem (MRCPSP) are problem-dependent. This paper first proposes an adaptive data-driven meta-learning Meta-heuristic Recommendation Model (MRM) to solve MRCPSP intelligently and efficiently. By learning the association between problem meta-features and algorithm performance, MRM can identify the most appropriate algorithm for different MRCPSPs. Multiclass Support Vector Machine (MCSVM) are integrated to train the classifiers for predicting the performance of the candidate meta-heuristics. To validate the proposed MRM, the performance is evaluated and compared in terms of accuracy, precision, sensitivity, and comprehensive evaluation index. In the experiments of 4 scenarios with 2 strategies, the average optimization and prediction accuracies are higher than 90% without increase in computational complexity. Comprehensive experiments and numerical results demonstrate the outperforming performance of the proposed MRM across various MRCPSP.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aha, D. W., Generalizing from case studies: a case study, (Proc of the 9th International Conference on Machine Learning (1992), Morgan Kaufmann: Morgan Kaufmann Aberdeen), 1-10 |
| [2] | Ahmeti, A., & Musliu, N. , 2021. Hybridizing constraint programming and meta-heuristics for multi-mode resource-constrained multiple projects scheduling problem. . In Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling-PATAT (Vol. 1). |
| [3] | Asta, S.; Karapetyan, D.; Kheiri, A.; Özcan, E.; Parkes, A. J., Combining Monte-Carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem, Information Sciences, 373, 476-498 (2016) |
| [4] | N. Bhatt, A.T., A. Ganatra, 2012. A survey & current research challenges in meta learning approaches based on dataset characteristics. International Journal of Soft Computing 2, 239-247. 10.1.1.683.8572. |
| [5] | Bishop, C.M., 2006. Pattern Recognition and Machine Learning. in: Information Science and Statistics, Springer-Verlag New York. https://link.springer.com/book/9780387310732. · Zbl 1107.68072 |
| [6] | Blazewicz, J.; Lenstra, J. K.; Kan, A. H.G. R., Scheduling subject to resource constraints: classification and complexity, Discrete Applied Mathematics, 5, 1, 11-24 (1983) · Zbl 0516.68037 |
| [7] | Bouleimen, K. H.L., A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European Journal of Operational Research, 149, 268-281 (2003) · Zbl 1040.90015 |
| [8] | P. Brazdil, C.G.G.-C., C. Soares, R. Vilalta, 2009. Metalearning: Applications to Data Mining. Springer, Verlag Berlin, Heidelberg. · Zbl 1173.68625 |
| [9] | 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, 3-41 (1999) · Zbl 0937.90030 |
| [10] | Burke, E. K.; Gendreau, M.; Hyde, M.; Kendall, G.; Ochoa, G.; Özcan, E.; Qu, R., Hyper-heuristics: a survey of the state of the art, Journal of the Operational Research Society, 64, 12, 1695-1724 (2013) |
| [11] | Chakrabortty, R.K., Sarker, R., & Essam, D. L. , 2018. A comparative study of different integer linear programming approaches for resource-constrained project scheduling problems. In Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016, 227-242. |
| [12] | Chang, C. C.C.-J. L., LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol, 2, 1-27 (2011) |
| [13] | C.W. Chiang, Y.Q.H., W.Y. Wang, 2008. Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling. Journal of Intelligent and Fuzzy Systems 29, 345-358. https://content.iospress.com/articles/journal-of-intelligent-and-fuzzy-systems/ifs00404. · Zbl 1210.90177 |
| [14] | Chu, X.; Cai, F.; Cui, C.; Hu, M.; Li, L.i.; Qin, Q., Adaptive recommendation model using meta-learning for population-based algorithms, Information Sciences, 476, 192-210 (2019) |
| [15] | Coelho, J. M.V., Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers, European Journal of Operational Research, 213, 73-82 (2011) · Zbl 1237.90086 |
| [16] | Cooper, D. F., Heuristics for scheduling resource-constrained projects: an experimental investigation, Management Science, 22, 1186-1194 (1976) · Zbl 0326.90029 |
| [17] | Cui, J., & Yu, J., 2021. Research on Solving Combinatorial Optimization Problems Based on Hyper-heuristic Algorithms. In 2021 2nd International Conference on Computer Science and Management Technology (ICCSMT). 463-468. 10.1109/ICCSMT54525.2021.00091. |
| [18] | Cui, C.; Hu, M.; Weir, J. D.; Wu, T., A recommendation system for meta-modeling: a meta-learning based approach, Expert Systems with Applications, 46, 33-44 (2016) |
| [19] | Cui, C.; Wu, T.; Hu, M.; Weir, J. D.; Li, X., Short-term building energy model recommendation system: a meta-learning approach, Applied Energy, 172, 251-263 (2016) |
| [20] | J. Czogalla, A.F., 2009. Fitness landscape analysis for the resource constrained project scheduling problem. in: International Conference on Learning and Intelligent Optimization LION 2009: Learning and Intelligent Optimization, 104-118. doi: 10.1007/978-3-642-11169-3_8. |
| [21] | Damak, N.; Jarboui, B.; Siarry, P.; Loukil, T., Differential evolution for solving multi-mode resource-constrained project scheduling problems, Computers & Operations Research, 36, 9, 2653-2659 (2009) · Zbl 1179.90134 |
| [22] | Elloumiab, S. P.F., A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem, European Journal of Operational Research, 205, 31-41 (2010) · Zbl 1188.90093 |
| [23] | Giraud-Carrier, C.; Vilalta, R.; Brazdil, P., Introduction to the special issue on meta-learning, Machine Learning, 54, 3, 187-193 (2004) |
| [24] | Gutierrez-Rodríguez, A. E.; Conant-Pablos, S. E.; Ortiz-Bayliss, J. C.; Terashima-Marín, H., Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning, Expert Systems with Applications, 118, 470-481 (2019) |
| [25] | Hartmann, S., Project scheduling with multiple modes: a genetic algorithm, Annals of Operations Research, 102, 111-135 (2001) · Zbl 1024.90039 |
| [26] | Hartmann, S. D., A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207, 1-14 (2010) · Zbl 1205.90123 |
| [27] | C.W. Hsu, C.C.C., C.J. Lin, 2016. A practical guide to support vector classification. https://www.csie.ntu.edu.tw/∼cjlin/libsvm. |
| [28] | Huerta, I. I.; Neira, D. A.; Ortega, D. A.; Varas, V.; Godoy, J.; Asín-Achá, R., Improving the state-of-the-art in the Traveling Salesman Problem: An Anytime Automatic Algorithm Selection, Expert Systems with Applications, 187, 115948 (2022) |
| [29] | F. Hutter, L.X., H.H. Hoos, K. Leyton-Brown, 2014. Algorithm runtime prediction: methods & evaluation. Artificial Intelligence Review 206, 79-111. doi: 10.1016/j.artint.2013.10.003. · Zbl 1334.68185 |
| [30] | Jarboui, B.; Damak, N.; Siarry, P.; Rebai, A., A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems, Applied Mathematics Computation, 195, 1, 299-308 (2008) · Zbl 1180.90125 |
| [31] | J. Józefowska, M.M., R. Różycki, G. Waligóra, J. Węglarz, 2001. Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research 102, 137-155. doi: 10.1023/A:1010954031930. · Zbl 0990.90513 |
| [32] | Kanda, J.; Carvalho, A.d.; Hruschka, E.; Soares, C.; Brazdil, P., Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: a comparison of meta-features, Neurocomputing, 205, 393-406 (2016) |
| [33] | Karaboga, D. B.b., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, Journal of Global Optimization, 39, 459-471 (2007) · Zbl 1149.90186 |
| [34] | Kerschke, P.; Hoos, H. H.; Neumann, F.; Trautmann, H., Automated algorithm selection: Survey and perspectives, Evolutionary computation, 27, 1, 3-45 (2019) |
| [35] | KhudaBukhsh, A. R.; Xu, L.; Hoos, H. H.; Leyton-Brown, K., SATenstein: Automatically building local search SAT solvers from components, Artificial Intelligence Review, 232, 20-42 (2016) · Zbl 1351.68255 |
| [36] | King, R. D.; Feng, C.; Sutherland, A., STATLOG: comparison of classification algorithms on large real-world problems, Applied Artificial Intelligence, 9, 3, 289-333 (1995) |
| [37] | Kolisch, R. A.S., PSPLIB-A project scheduling problem library, European Journal of Operational Research, 96, 205-216 (1997) · Zbl 0947.90587 |
| [38] | Lemke, C.; Budka, M.; Gabrys, B., Metalearning: a survey of trends and technologies, Artificial Intelligence Review, 44, 1, 117-130 (2015) |
| [39] | Li, H. H.Z., Ant colony optimization-based multi-mode scheduling under renewable and nonrenewable resource constraints, Automation in Construction, 35, 431-438 (2013) |
| [40] | Liu, H.; Fang, Z.; Li, R., Credibility-based chance-constrained multimode resource-constrained project scheduling problem under fuzzy uncertainty, Computers & Industrial Engineering, 171, 108402 (2022) |
| [41] | Lova, A.; Tormos, P.; Cervantes, M.; Barber, F., An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International Journal of Production Economics, 117, 2, 302-316 (2009) |
| [42] | Malan, K. M.A. P.E., A survey of techniques for characterising fitness landscapes and some possible ways forward, Information Sciences, 241, 148-163 (2013) |
| [43] | V. Mandhala, V.S., B. Devi, 2014. Scene classification using support vector machines. Journal of Theoretical & Applied Information Technology, 1807-1810. https://ieeexplore.ieee.org/document/7019421. |
| [44] | Márkus, A.; Váncza, J.; Kis, T.; Kovács, A., Project scheduling approach to production planning, CIRP Annals, 52, 359-362 (2003) |
| [45] | Mastor, A. A., An experimental investigation and comparative evaluation of production line balancing techniques, Management Science, 16, 728-746 (1970) · Zbl 0217.26903 |
| [46] | Messelis, T. P.D. C., An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem, European Journal of Operational Research, 233, 511-528 (2014) · Zbl 1339.90143 |
| [47] | Mika, M.; Waligóra, G.; Węglarz, J., Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times, European Journal of Operational Research, 187, 3, 1238-1250 (2008) · Zbl 1137.90508 |
| [48] | Miranda, P. B.C.; Prudêncio, R. B.C.; Pappa, G. L., H3AD: A hybrid hyper-heuristic for algorithm design, Information Sciences, 414, 340-354 (2017) |
| [49] | Mu, T.; Wang, H.; Wang, C.; Liang, Z.; Shao, X., Auto-CASH: A meta-learning embedding approach for autonomous classification algorithm selection, Information Sciences, 591, 344-364 (2022) |
| [50] | M.A. Muñoz, M.K., S.K. Halgamuge, 2012. A meta-learning prediction model of algorithm performance for continuous optimization problems. in: International Conference on Parallel Problem Solving From Nature, 226-235. doi: 10.1007/978-3-642-32937-1_23. |
| [51] | Muñoz, M. A.; Sun, Y.; Kirley, M.; Halgamuge, S. K., Algorithm selection for black-box continuous optimization problems: a survey on methods and challenges, Information Sciences, 317, 224-245 (2015) |
| [52] | Nemati-Lafmejani, R.; Davari-Ardakani, H.; Najafzad, H., Multi-mode resource constrained project scheduling and contractor selection: Mathematical formulation and metaheuristic algorithms, Applied Soft Computing, 81, 105533 (2019) |
| [53] | Pascoe, T. L., Allocation of resources CPM, Revue Francaise Recherche Operationelle, 38, 31-38 (1966) |
| [54] | Patterson, J. H., Project scheduling: The effects of problem structure on heuristic performance, Naval Research Logistics Quarterly, 23, 1, 95-123 (1976) · Zbl 0325.90027 |
| [55] | Pellerin, R.; Perrier, N.; Berthaut, F., A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, European Journal of Operational Research, 280, 395-416 (2020) · Zbl 1430.90286 |
| [56] | F. Peng, K.T., G. Chen, X. Yao, 2010. Population-based algorithm portfolios for numerical optimization. IEEE Transactions on Evolutionary Computation 14, 782-800. https://ieeexplore.ieee.org/document/5439827. |
| [57] | Peteghem, V. V.M. V., Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem, Journal of Heuristics, 17, 705-728 (2011) · Zbl 1237.90100 |
| [58] | A. R. Pourghaderi, S.A.T., J. Talebi, 2008. Scatter search for multi-mode resource-constrained project scheduling problems. in: IEEE International Conference on Industrial Engineering and Engineering Management, 163-167. https://ieeexplore.ieee.org/document/4737852. |
| [59] | Rendell, L. H.C., Empirical learning as a function of concept character, Machine Learning, 5, 267-298 (1990) |
| [60] | Reyck, B. D.W. H., On the use of the complexity index as a measure of complexity in activity networks, European Journal of Operational Research, 91, 347-366 (1996) · Zbl 0924.90092 |
| [61] | L.C. Reyes, C.G.S., J.P. Ortega, V. Landero, M. Quiroz, A. Ochoa, 2012. Algorithm selection: from meta-learning to hyper-heuristics. in: Intelligent Systems, 77-102. 10.5772/36710. |
| [62] | Rice, J. R., The Algorithm Selection Problem, Advances in Computers, 15, 65-118 (1976) |
| [63] | Rosłon, J. H.; Kulejewski, J. E., A hybrid approach for solving multi-mode resource-constrained project scheduling problem in construction, Open Engineering, 9, 7-13 (2019) |
| [64] | Schiavinotto, T. T.S., A review of metrics on permutations for search landscape analysis, Computers & Operations Research, 34, 3143-3153 (2007) · Zbl 1185.90115 |
| [65] | H. Shen, X.L., 2013. Cooperative discrete particle swarms for multi-mode resource-constrained projects. in: IEEE International Conference on Computer Supported Cooperative Work in Design, 31-36. https://ieeexplore.ieee.org/document/6580935. |
| [66] | Smith-Miles, K. A., Cross-disciplinary perspectives on meta-learning for algorithm selection, ACM Computing Surveys, 41, 1-25 (2009) |
| [67] | Smith-Miles, K. S.B., Generating new test instances by evolving in instance space, Computers & Operations Research, 63, 102-113 (2015) · Zbl 1349.68325 |
| [68] | Smith-Miles, K.; Baatar, D.; Wreford, B.; Lewis, R., Towards objective measures of algorithm performance across instance space, Computers & Operations Research, 45, 12-24 (2014) · Zbl 1348.90646 |
| [69] | K.J.V.H. Smith-Miles, 2011. Discovering the suitability of optimisation algorithms by learning from evolved instances. Annals of Mathematics & Artificial Intelligence 61, 87-104. doi: 10.1007/s10472-011-9230-5. · Zbl 1236.49008 |
| [70] | Sprecher, A. A.D., Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm, European Journal of Operational Research, 107, 431-450 (1998) · Zbl 0943.90042 |
| [71] | Sprecher, A.; Hartmann, S.; Drexl, A., An exact algorithm for project scheduling with multiple modes, Operations-Research-Spektrum, 19, 3, 195-203 (1997) · Zbl 0885.90059 |
| [72] | Strassl, S.; Musliu, N., Instance space analysis and algorithm selection for the job shop scheduling problem, Computers & Operations Research, 141, 105661 (2022) · Zbl 1511.90216 |
| [73] | Van Peteghem, V. M.V., An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances, European Journal of Operational Research, 235, 62-72 (2014) · Zbl 1305.90203 |
| [74] | Vilalta, R. Y.D., A perspective view and survey of meta-learning, Artificial Intelligence Review, 2, 77-95 (2002) |
| [75] | Wang, L. C.F., An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem, Information Sciences, 181, 4804-4822 (2011) · Zbl 1242.90082 |
| [76] | Wang, L. C.F., An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem, Computers & Operations Research, 39, 449-460 (2012) |
| [77] | Wang, Y.u.; Li, B.; Weise, T.; Wang, J.; Yuan, B.o.; Tian, Q., Self-adaptive learning based particle swarm optimization, Information Sciences, 181, 20, 4515-4538 (2011) · Zbl 1242.68297 |
| [78] | Wolpert, D. H.W. G.M., No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation, 1, 205-216 (1997) |
| [79] | Wu, G.; Mallipeddi, R.; Suganthan, P. N., Ensemble strategies for population-based optimization algorithms - A survey, Swarm and Evolutionary Computation, 44, 695-711 (2019) |
| [80] | Xie, F.; Li, H.; Xu, Z., Multi-mode resource-constrained project scheduling with uncertain activity cost, Expert Systems with Applications, 168, 114475 (2021) |
| [81] | Yuan, Y.; Ye, S.; Lin, L.; Gen, M., Multi-objective multi-mode resource-constrained project scheduling with fuzzy activity durations in prefabricated building construction, Computers & Industrial Engineering, 158, 107316 (2021) |
| [82] | Zhang, H.; Tam, C. M.; Li, H., Multimode project scheduling based on particle swarm optimization, Computer-aided Civil Infrastructure Engineering, 21, 2, 93-103 (2006) |
| [83] | Chu, X.; Wu, T.; Weir, J. D.; Shi, Y.; Niu, B.; Li, L.., Learning-Interaction-Diversification framework for swarm intelligence optimizers: A unified perspective, Neural Computing and Applications, 32, 1789-1809 (2020) |
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.
