单机早/迟惩罚任务的调度问题 - 基于机器学习的算法选择方法

Aug 6, 2026

The algorithm selection paradigm is applied to the Single Machine Scheduling Problem with Early/Tardy jobs, aiming to select the most accurate optimization algorithm for each instance using machine learning. Three state-of-the-art metaheuristics—genetic algorithm, particle swarm optimization, and tabu search—are adapted within a unified framework. Runtime and the cost function are combined to build a new performance criterion. A dataset of 98,000 instances with 12 descriptive features is generated, with statistical comparisons and evaluation of 10 classifiers, where Dagging with Random Forest achieves the highest accuracy of 88.44%.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

AccessFree to download

Introduction

Problem definition and objective

Existing exact methods and limitations

Algorithm selection framework

Adapted metaheuristics

Performance criterion based on runtime and cost

Experimental setup and results

Instance generation and features

Statistical comparisons and classifier evaluation

[www.bizinfo.edu.rs](www.bizinfo.edu.rs) A machine learning-based selection approach for solving the single machine scheduling problem with Early/Tardy jobs Pristup odabira zasnovan na mašinskom učenju za rešavanje problema rasporeda jedne mašine saranim/kasnim zadacima Ahmed-Adnane Abdessemeda􀀍 , Leila-Hayet Moussa, Khaled Benaggounea, Toufik Bentrciaa a University of Batna 2, Laboratory of Automation and Production Engineering (LAP), Department of Industrial Engineering, Batna, Algeria A r t i c l e i n f o Original scientific paper/ Originalannaučni rad Received/ Rukopis je primljen: 31 July, 2023 Revised/ Korigovan: 1 January, 2024 Accepted/ Prihvaćen: 2 February, 2024 DOI: [https://doi.org/10.5937/bizinfo2401001A](https://doi.org/10.5937/bizinfo2401001A) UDC/ UDK: 004.85 A b s t r a c t 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 metaheuristics 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 S a ž e t a k Danas je paradigma izbora algoritama jedan od obećavajućih pristupa u oblasti optimizacijskih problema. Njegov glavni ciljje dareši svaki slučaj problema optimizacije najtačnijim algoritmom koristeći tehnike mašinskog učenja. Ovaj rad obrađuje pitanje izbora algoritma za problem raspoređivanja jedne mašine sa ranim/kasnim zadacima prilagođavanjem tri meta-heuristike iznajnovije tehnike, odnosno genetskog algoritma, optimizacije roja čestica i tabu pretraživanja. Upredloženom okviru kombinujemo vreme rada i funkciju troškova da bismo dobili novi kriterijum učinka. Generišese veliki skup sastavljen od 98000 instanci problemasa 12 karakteristika koje karakterišu svaku instancu. Izvodimo statističko poređenje implementirane metaheuristike i procenjujemo 10 klasifikatora. Možesezaključiti da je Dagging algoritam u kombinaciji sa Random Forestom najverovatnije najbolji klasifikator, koji postiže 88,44% maksimalne tačnosti. Ključne reči: problem raspoređivanja jedne mašine, rani/kasni zadaci, izbor algoritma, mašinsko učenje, metaheuristika 1. Introduction Current technological advancements in industrial systems have offered a substantial opportunity, which helped the boost of the organization’s production ability to meet the customer’s expectations such as the delivery date. For this reason, most modern production and manufacturing systems follow robust and well-defined philosophies including flexible manufacturing systems, and just in time (Chan et al., 2010) . In fact, unpredicted challenges such as 􀀍Corresponding author E-mail address: [adnane.abdessemed@univ-batna2.dz](adnane.abdessemed@univ-batna2.dz)[ ](adnane.abdessemed@univ-batna2.dz)This is an open access paper under the license the early or late product delivery times do negatively affect the total production charges. So, numerous studies have been conducted in the literature to remedy this problem. The Single Machine Scheduling Problem, including Earliness/Tardiness penalties and distinct due dates (SMSPET), is amongs

FAQs

本文研究的核心问题是什么？

研究算法选择以求解“单机早/迟（Earliness/Tardiness）任务调度问题”，目标是在不同实例上选择更准确的优化算法以最小化早到与迟到惩罚总和。

提出的框架如何结合机器学习与元启发式算法？

将遗传算法、粒子群优化和禁忌搜索三种元启发式进行适配，并在框架中使用机器学习完成算法选择，同时将运行时间与代价函数合成为新的性能准则。

数据集与分类器评估结果如何？

生成包含98,000个实例的数据集，每个实例用12个特征表征；对已实现的元启发式进行统计比较并评估10个分类器。结果显示，Dagging 与 Random Forest 组合取得最高准确率88.44%。

Aug 6, 2026

Upload by Olivia Brown