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

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.

Keywords

• single machine scheduling problem
• early/tardy jobs
• algorithm selection
• machine learning
• meta-heuristics