A machine learning-based selection approach for solving the single machine scheduling problem with Early/Tardy jobs

Ahmed Adnane Abdessemed; Leila Hayet  Mouss; Khaled Benaggoune; Toufik Bentrcia

doi:10.5937/bizinfo2401001A

Authors

Ahmed Adnane Abdessemed University of Batna 2, Laboratory of Automation and Production Engineering (LAP), Department of Industrial Engineering, Batna, Algeria
Leila Hayet Mouss University of Batna 2, Laboratory of Automation and Production Engineering (LAP), Department of Industrial Engineering, Batna, Algeria
Khaled Benaggoune University of Batna 2, Laboratory of Automation and Production Engineering (LAP), Department of Industrial Engineering, Batna, Algeria
Toufik Bentrcia University of Batna 2, Laboratory of Automation and Production Engineering (LAP), Department of Industrial Engineering, Batna, Algeria

DOI:

https://doi.org/10.5937/bizinfo2401001A

Keywords:

Single machine scheduling problem, Early/Tardy jobs, Algorithm selection, Machine learning, Meta-heuristics

Abstract

Today, the algorithm selection paradigm has become one of the promising approaches in the field of optimization problems. Its main goal is to solve each case of an optimization problem with the most accurate algorithm using machine learning techniques. This paper treats the issue of the algorithm selection for the Single Machine Scheduling Problem with Early/Tardy jobs by adapting three meta-heuristics from the state-of-the-art, namely genetic algorithm, particle swarm optimization, and tabu search. In the proposed framework, we combine the running time and the cost function to get a new performance criterion. A large set composed of 98000 instances of the problem is generated with 12 features characterizing each instance. We carry a statistical comparison of the implemented meta-heuristics, and we evaluate 10 classifiers. It can be deduced that the Dagging algorithm combined with the Random Forest is the most likely to be the best classifier, which achieves 88.44% of the maximum accuracy.

Downloads

Download data is not yet available.

References

Abdul-Razaq, T. S., & Potts, C. N. (1988). Dynamic programming state-space relaxation for single-machine scheduling. Journal of the Operational Research Society, 39(2), 141-152. https://doi.org/10.1057/jors.1988.26

Baker, K. R., & Martin, J. B. (1974). An experimental comparison of solution algorithms for the single-machine tardiness problem. Naval Research Logistics Quarterly, 21(1), 187-199. https://doi.org/10.1002/nav.3800210114

Chan, H. K., Yin, S., & Chan, F. T. (2010). Implementing just-in-time philosophy to reverse logistics systems: a review. International Journal of Production Research, 48(21), 6293-6313. https://doi.org/10.1080/00207540903225213

Chang, P. C., Chen, S. S., & Fan, C. Y. (2008). Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems. Applied Soft Computing, 8(1), 767-777. https://doi.org/10.1016/j.asoc.2007.06.005.

Eberhart, R., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In MHS'95. Proceedings of the sixth international symposium on micro machine and human science (pp. 39-43). IEEE. https://doi.org/10.1109/MHS.1995.494215

Fernández-Delgado, M., Cernadas, E., Barro, S., & Amorim, D. (2014). Do we need hundreds of classifiers to solve real world classification problems?. The journal of machine learning research, 15(1), 3133-3181.

Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, 1(3), 190-206. https://doi.org/10.1287/ijoc.1.3.190

Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94. https://doi.org/10.1287/inte.20.4.74

Guo, H., & Hsu, W. H. (2007). A machine learning approach to algorithm selection for NP-hard optimization problems: a case study on the MPE problem. Annals of Operations Research, 156(1), 61. https://doi.org/10.1007/s10479-007-0229-6

Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The WEKA data mining software: an update. ACM SIGKDD explorations newsletter, 11(1), 10-18. https://doi.org/10.1145/1656274.1656278

Hao, P., Wang, Z., Wu, G., Boriboonsomsin, K., & Barth, M. (2017, October). Intra-platoon vehicle sequence optimization for eco-cooperative adaptive cruise control. In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC) (pp. 1-6). IEEE. https://doi.org/10.1109/ITSC.2017.8317879

Ho, Y. C., & Pepyne, D. L. (2001, December). Simple explanation of the no free lunch theorem of optimization. In Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No. 01CH37228) (Vol. 5, pp. 4409-4414). IEEE. https://doi.org/10.1109/CDC.2001.980896.

Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.

Kanda, J., Carvalho, A., Hruschka, E., & Soares, C. (2011). Selection of algorithms to solve traveling salesman problems using meta-learning. International Journal of Hybrid Intelligent Systems, 8(3), 117-128. https://doi.org/10.3233/HIS-2011-0133

Kerschke, P., Hoos, H. H., Neumann, F., & Trautmann, H. (2019). Automated algorithm selection: Survey and perspectives. Evolutionary computation, 27(1), 3-45. https://doi.org/10.1162/evco_a_00242

Laguna, M., Barnes, J. W., & Glover, F. W. (1991). Tabu search methods for a single machine scheduling problem. Journal of Intelligent Manufacturing, 2, 63-73. https://doi.org/10.1007/BF01471219

Lindauer, M., Hoos, H. H., Hutter, F., & Schaub, T. (2015). Autofolio: An automatically configured algorithm selector. Journal of Artificial Intelligence Research, 53, 745-778. https://doi.org/10.1613/jair.4726

M’Hallah, R., & Alhajraf, A. (2016). Ant colony systems for the single-machine total weighted earliness tardiness scheduling problem. Journal of Scheduling, 19, 191-205. https://doi.org/10.1007/s10951-015-0429-x

Messelis, T., & De Causmaecker, P. (2014). An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 233(3), 511-528. https://doi.org/10.1016/j.ejor.2013.08.021

Nudelman, E., Leyton-Brown, K., Devkar, A., Shoham, Y., & Hoos, H. (2004). Satzilla: An algorithm portfolio for SAT. Solver description, SAT competition, 2004.

Ow, P. S., & Morton, T. E. (1989). The single machine early/tardy problem. Management science, 35(2), 177-191. https://doi.org/10.1287/mnsc.35.2.177

Pihera, J., & Musliu, N. (2014, November). Application of machine learning to algorithm selection for TSP. In 2014 IEEE 26th International Conference on Tools with Artificial Intelligence (pp. 47-54). IEEE. https://doi.org/10.1109/ICTAI.2014.18

Pinedo, M. L. (2012). Scheduling (Vol. 29). New York: Springer. https://doi.org/10.1007/978-3-319-26580-3

Rice, J. R. (1976). The algorithm selection problem. In Advances in computers (Vol. 15, pp. 65-118). Elsevier. https://doi.org/10.1016/S0065-2458(08)60520-3

Sammut, C., & Webb, G. I. (Eds.). (2011). Encyclopedia of machine learning. Springer Science & Business Media. https://doi.org/10.1007/978-0-387-30164-8

Scott, J., Niemetz, A., Preiner, M., Nejati, S., & Ganesh, V. (2023). Algorithm selection for SMT: MachSMT: Machine Learning Driven Algorithm Selection for SMT Solvers. International Journal on Software Tools for Technology Transfer, 1-21. https://doi.org/10.1007/s10009-023-00696-0

Smith-Miles, K. A. (2009). Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Computing Surveys (CSUR), 41(1), 1-25. https://doi.org/10.1145/1456650.1456656

Smith-Miles, K., Baatar, D., Wreford, B., & Lewis, R. (2014). Towards objective measures of algorithm performance across instance space. Computers & Operations Research, 45, 12-24. https://doi.org/10.1016/j.cor.2013.11.015

Smith-Miles, K., James, R., Giffin, J., & Tu, Y. (2009). Understanding the relationship between scheduling problem structure and heuristic performance using knowledge discovery. Learning and Intelligent Optimization, LION, 3.

Sourd, F. (2009). New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS Journal on Computing, 21(1), 167-175. https://doi.org/10.1287/ijoc.1080.0287

Sourd, F., & Kedad-Sidhoum, S. (2005). An efficient algorithm for the earliness-tardiness scheduling problem. Optimisation Online,(1205).

Tanaka, S., Fujikuma, S., & Araki, M. (2009). An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling, 12, 575-593. https://doi.org/10.1007/s10951-008-0093-5

Tasgetiren, M. F., Sevkli, M., Liang, Y. C., & Gençyilmaz, G. (2004, June). Particle swarm optimization algorithm for single machine total weighted tardiness problem. In Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753) (Vol. 2, pp. 1412-1419). IEEE. https://doi.org/10.1109/CEC.2004.1331062

Tsai, T. I. (2007). A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. The International Journal of Advanced Manufacturing Technology, 31(9-10), 994-1000. https://doi.org/10.1007/s00170-005-0261-0

Valente, J. M. (2007). Heuristics for the single machine scheduling problem with early and quadratic tardy penalties. European Journal of Industrial Engineering, 1(4), 431-448. https://doi.org/10.1504/EJIE.2007.015391

Wagner, M., Lindauer, M., Mısır, M., Nallaperuma, S., & Hutter, F. (2018). A case study of algorithm selection for the traveling thief problem. Journal of Heuristics, 24, 295-320. https://doi.org/10.1007/s10732-017-9328-y

Wan, G., & Yen, B. P. C. (2002). Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research, 142(2), 271-281. https://doi.org/10.1016/S0377-2217(01)00302-2

Xu, L., Hutter, F., Shen, J., Hoos, H. H., & Leyton-Brown, K. (2012). SATzilla2012: Improved algorithm selection based on cost-sensitive classification models. Proceedings of SAT Challenge, 57-58.

Yau, H., Pan, Y., & Shi, L. (2008). New solution approaches to the general single-machine earliness-tardiness problem. IEEE Transactions on Automation Science and Engineering, 5(2), 349-360. https://doi.org/10.1109/TASE.2007.895219