=Paper=
{{Paper
|id=Vol-3812/paper6
|storemode=property
|title=Developing an Algorithm Selector for Green Configuration in Scheduling Problems
|pdfUrl=https://ceur-ws.org/Vol-3812/paper6.pdf
|volume=Vol-3812
|authors=Carlos March Moya,Christian Perez,Miguel A. Salido
|dblpUrl=https://dblp.org/rec/conf/confws/MoyaPS24
}}
==Developing an Algorithm Selector for Green Configuration in Scheduling Problems==
https://ceur-ws.org/Vol-3812/paper6.pdf
Developing an Algorithm Selector for Green Configuration in
Scheduling Problems
Carlos March1,*,† , Christian Pérez1,2,† and Miguel Salido1
1
Universitat Politècnica de València, Instituto de Automática e Informática Industrial, Camì de Vera S/N, Valencia, Spain
2
Universitat Politècnica de València, valgrAI - Valencian Graduate School and Research Network of Artificial Intelligence, Camì de Vera S/N, Valencia, Spain
Abstract
The Job Shop Scheduling Problem (JSP) is central to operations research, primarily optimizing energy efficiency due to its profound
environmental and economic implications. Efficient scheduling enhances production metrics and mitigates energy consumption, thus
effectively balancing productivity and sustainability objectives. Given the intricate and diverse nature of JSP instances, along with
the array of algorithms developed to tackle these challenges, an intelligent algorithm selection tool becomes paramount. This paper
introduces a framework designed to identify key problem features that characterize its complexity and guide the selection of suitable
algorithms. Leveraging machine learning techniques, particularly XGBoost, the framework recommends optimal solvers such as GUROBI,
CPLEX, and GECODE for efficient JSP scheduling. GUROBI excels with smaller instances, while GECODE demonstrates robust scalability
for complex scenarios. The proposed algorithm selector achieves an accuracy of 84.51% in recommending the best algorithm for solving
new JSP instances, highlighting its efficacy in algorithm selection. By refining feature extraction methodologies, the framework aims to
broaden its applicability across diverse JSP scenarios, thereby advancing efficiency and sustainability in manufacturing logistics.
Keywords
Job Shop Scheduling Problem, Energy Efficiency, Algorithm Selection, Machine Learning, Feature Extraction
1. Introduction mize energy consumption while maintaining productivity
[8]. Advanced algorithms and optimization techniques have
The Job Shop Scheduling Problem (JSP) is a cornerstone been developed to address these energy-related challenges,
issue in operations research and optimization, serving as a taking into account factors like machine speed, idle time,
critical benchmark for assessing the performance of various and energy requirements [9]. Real-world implementations
algorithms. JSP entails the complex task of scheduling jobs of these strategies have demonstrated tangible benefits, in-
on machines in a manufacturing environment to optimize cluding cost savings and positive environmental effects [10].
several performance metrics, such as makespan, flow time, In addition to traditional optimization methods, machine
tardiness, resource utilization, and energy consumption [1]. learning techniques are increasingly being utilized to rec-
Effective benchmarking of JSP solutions requires a multi- ommend algorithms for solving problems within the JSP
faceted evaluation of these metrics, particularly focusing family. For instance, Müller et al. designed a system capable
on makespan, energy consumption, and tardiness to gauge of selecting the most suitable solver for addressing Flex-
scheduling efficiency and resource utilization [2]. Tools like ible JSP by leveraging machine learning approaches [11].
JSPLIB play a vital role in these benchmarking efforts by Similarly, Strassl and Musliu [12] analyzed JSP instances
providing researchers with diverse instances derived from without energy consumption from the literature to extract
significant studies and experiments, thereby enhancing the features that inform algorithm performance, resulting in a
evaluation of algorithms [3]. homogeneous set of instances with consistent characteris-
Understanding the characteristics of problem instances tics. These features were then used to train various models,
is essential for effective benchmarking in JSP. Critical fac- with Random Forest achieving the highest accuracy at 90%
tors include the number of jobs and machines, variability [12].
in processing times, machine availability, and precedence In conclusion, the integration of machine learning tech-
relationships, all of which significantly impact algorithm niques into JSP research provides new avenues for improv-
performance [4]. Additionally, considering energy consump- ing algorithm selection and performance, particularly in
tion, which varies based on machine speed and operational handling complex and varied instances. This integration en-
factors, adds another layer of complexity [5]. Achieving a hances the efficiency and effectiveness of job shop schedul-
balance between energy consumption and scheduling de- ing by combining the strengths of traditional optimization
cisions is crucial for attaining energy efficiency without approaches with innovative machine learning methods. The
compromising production goals [6]. ongoing advancements in this field are driving both aca-
JSP’s focus on energy efficiency has intensified in recent demic research and practical applications toward more sus-
years due to its substantial environmental and economic im- tainable and innovative solutions.
pacts [7]. Researchers have investigated strategies such as
employing speed-adjustable machines and vehicles to mini-
2. Problem Description and Model
ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, 2024,
Girona, Spain Formulation
*
Corresponding author.
†
These authors contributed equally. The JSP tackled in this study emphasizes its intricate energy
$ cmarmoy@upv.es (C. March); cripeber@upv.es (C. Pérez); considerations. The JSP poses a significant computational
msalido@upv.es (M. Salido) challenge, being NP-complete due to its difficulty finding
https://gps.blogs.upv.es/ (C. March); https://gps.blogs.upv.es/ optimal solutions within reasonable time frames.
(C. Pérez); https://gps.blogs.upv.es/ (M. Salido)
The core challenge of the JSP involves optimizing task
0009-0009-7525-9133 (C. March); 0000-0002-9121-7939 (C. Pérez);
0000-0002-4835-4057 (M. Salido) allocation across multiple jobs and machines while minimiz-
© 2024 This work is licensed under a “CC BY 4.0” license. ing key criteria, notably the total job completion time. How-
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
ever, achieving this optimization is complex due to various ∀𝑚 ∈ 𝑀, ∀𝑗 ∈ 𝐽,
real-world constraints and dependencies, contributing to ∀𝑡 ∈ 𝑇𝑗 , ∀𝑠 ∈ 𝑆, 𝑥𝑚𝑗𝑡𝑠 = 1
the JSP’s NP-completeness. The combinatorial explosion of
possible job and machine combinations further complicates
the problem, making exhaustive exploration impractical as 𝑐𝑚𝑗𝑠 ≥ 𝑐𝑚𝑖𝑝 + 𝑃𝑚𝑖𝑝𝑠 (6)
the number of jobs and machines grows. ∀𝑚 ∈ 𝑀, ∀𝑖, 𝑗 ∈ 𝐽,
∀𝑝, 𝑞 ∈ 𝑇𝑖 , 𝑇𝑗 , ∀𝑠 ∈ 𝑆,
2.1. Mixed Integer Programming 𝑖 ̸= 𝑗 ∧ 𝑝 < 𝑞 ∧ 𝑦𝑚𝑖𝑗𝑝𝑠 = 1
The JSP involves various sets, parameters, variables, and
constraints crucial for formulation and solution: 𝑐𝑚𝑗𝑡 ≥ 0 , 𝑡𝑚𝑗𝑡 ≥ 0 (7)
Sets: ∀𝑚 ∈ 𝑀, ∀𝑗 ∈ 𝐽∀𝑡 ∈ 𝑇𝑗
• 𝐽 = {1, . . . , 𝑛}, the set of jobs.
This model seeks the optimal solution 𝜑* that minimizes
• 𝑀 = {1, . . . , 𝑚}, the set of machines. the three measures mentioned in equation 1. considering
• 𝑆 = {1, . . . , 𝑠}, the set of speeds. the constraints associated: the maximum makespan of all
• 𝑇𝑗 , ∀𝑗 ∈ 𝐽, the set of tasks in job 𝑗. In standard JSP task jobs 𝑀 𝐾(𝜑), the total energy consumption 𝐸𝐶(𝜑),
𝑇𝑗 = 𝑀 . and the total tardiness 𝑇 𝑇 (𝜑). The simultaneous optimiza-
Parameters: tion of these objectives requires a delicate balance between
the various considerations and constraints of the problem.
• 𝐷𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , the due date of task job 𝑡𝑗𝑡 . Therefore, two approaches to optimizing the problem so-
• 𝑅𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , the release date of task job lutions are proposed, allowing us to analyze the methods’
𝑡𝑗𝑡 . behavior better.
• 𝑃𝑗𝑡𝑠 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , the processing time of task
job 𝑡𝑗𝑡 on machine 𝑡 with speed 𝑠. 2.2. Mono-objective optimization
• 𝐸𝑗𝑡𝑠 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , the energy consumption for
processing task job 𝑡𝑗𝑡 with speed 𝑠. This section presents the mono-objective optimization for
a specific scheduling problem involving multiple jobs and
Variables: machines, emphasizing key performance metrics such as
makespan, energy consumption, and total tardiness.
• 𝑐𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , the completion time of task
job 𝑡𝑗𝑡
• 𝑡𝑡𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 , tardiness of task job 𝑡𝑗𝑡 with 𝑓 𝑚 = max (𝑐𝑗𝑚 ) (8)
respect to its due date 𝑗∈𝐽
𝑚∈𝑀
• 𝑥𝑚𝑗𝑡𝑠 ∈ {0, 1}, ∀𝑚 ∈ 𝑀 , ∀𝑗 ∈ 𝐽, 𝑡 ∈ 𝑇𝑗 , binary ∑︁ ∑︁
𝑓𝑒 = 𝐸𝑗𝑡 (9)
sequencing variables (i.e., 𝑥𝑚𝑗𝑡𝑠 = 1 denotes that
𝑗∈𝐽 𝑡∈𝑇𝑗
task 𝑡 of job 𝑗 is performed with speed 𝑠 on machine ∑︁ ∑︁ ∑︁
𝑚) 𝑓 𝑡𝑡 = 𝑡𝑡𝑚𝑗𝑡 (10)
• 𝑦𝑚𝑖𝑗𝑝𝑞 ∈ {0, 1}, ∀𝑚 ∈ 𝑀 , ∀𝑖, 𝑗 ∈ 𝐽, ∀𝑝, 𝑞 ∈ 𝑚∈𝑀 𝑗∈𝐽 𝑡∈𝑇𝑗
𝑇𝑖 , 𝑇𝑗 , 𝑖 ̸= 𝑗, binary assignment variables (i.e.,
𝑦𝑖𝑗𝑝𝑞 = 1 denotes that task 𝑝 of job 𝑖 precedes task Equation 8 represents the makespan, which is the maxi-
𝑞 of job 𝑗 on machine 𝑚) mum completion time among all machines, by calculating
the total processing time of all job tasks on each machine
and selecting the maximum value across all machines. Equa-
𝜑* = arg min [𝑀 𝐾(𝜑), 𝐸𝐶(𝜑), 𝑇 𝑇 (𝜑)] (1) tion 9 describes energy consumption by computing the total
𝜑∈Φ
energy consumed by all job tasks across all machines. Lastly,
subject to: Equation 10 is formulated to show the total tardiness, which
represents the number of time units of each job or operation
∑︁ that are performed outside its time window, i.e., the period
𝑥𝑚𝑗𝑡𝑠 = 1 (2) of time between the release date and the due date.
𝑚∈𝑀
∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑇𝑗 ∀𝑠 ∈ 𝑆
𝑓 𝑚 − 𝑚− 𝑓 𝑒 − 𝑚− 𝑓 𝑡𝑡
𝑚𝑖𝑛 1
− + 2
− + (11)
∑︁ 𝑚+1 − 𝑚1 𝑚+2 − 𝑚2 𝑚+1
𝑦𝑚𝑖𝑗𝑝𝑞 = 1 (3)
𝑚∈𝑀
Minimizing the objective Function 11 aims to find a so-
lution that achieves a balanced trade-off among the com-
∀𝑖, 𝑗 ∈ 𝐽, ∀𝑝, 𝑞 ∈ 𝑇𝑖 , 𝑇𝑗 ,
ponents. The values 𝑚+ 1,2 and 𝑚1,2 are used to normalize
−
𝑖 ̸= 𝑗, 𝑝 ≤ 𝑞 the 𝜑 solution obtained in the three-dimensional objective
*
space. This allows a correct comparison between the values
𝑡𝑡𝑚𝑗𝑡 ≥ 𝑐𝑚𝑗𝑡 − 𝐷𝑗𝑡 (4) of the objective function in minimizing the problem, giving
the same weight to all the parts, and avoiding any of the
∀𝑚 ∈ 𝑀, ∀𝑗 ∈ 𝐽, variables dominating the search.
∀𝑡 ∈ 𝑇𝑗 , 𝑥𝑚𝑗𝑡 = 1
∑︁ ∑︁
𝑚+
1 = ( max(𝑃𝑗𝑚𝑠 )) (12)
𝑐𝑚𝑗𝑡 ≥ 𝑅𝑗𝑡 + 𝑃𝑚𝑗𝑡𝑠 (5) 𝑗∈𝐽 𝑚∈𝑀
𝑠∈𝑆
∑︁ ∑︁
𝑚+
2 = ( max(𝐸𝑗𝑚𝑠 )) (13) tive as possible about the complexity of the instance they
𝑠∈𝑆
𝑚∈𝑀 𝑗∈𝐽 represent. The extra features extracted are:
∑︁
𝑚−
1 = max( min(𝑃𝑗𝑚𝑠 )) (14)
𝑗∈𝐽
𝑚∈𝑀
𝑠∈𝑆 max(𝑃 ) (16)
∑︁ ∑︁
𝑚−
2 = ( min(𝐸𝑗𝑚𝑠 )) (15)
𝑚∈𝑀 𝑗∈𝐽
𝑠∈𝑆 mean(𝑃 ) (17)
Equations between 12 and 15 determine both maxi-
min(𝑃 ) (18)
mum (𝑚+ 1 and 𝑚2 ) and minimum (𝑚1 and 𝑚2 ) values
+ − −
for makespan and energy consumption respectively. For The maximum processing time (16) represents the longest
makespan, these values signify the maximum and minimum time required to complete any single operation within the
completion times across all machines, accounting for the job set. The mean processing time ( Equation 17) gives
maximum and minimum processing times of job tasks on the average duration of the operations, providing an over-
each machine. Similarly, in terms of energy consumption, all sense of the job length. The minimum processing time
they represent the maximum and minimum energy utilized (Equation 18) shows the shortest time needed for any oper-
among all machines, considering the maximum and mini- ation, indicating the fastest job segment.
mum energy consumption of all job tasks on each machine.
max(𝐸) (19)
3. Algorithm Selector mean(𝐸) (20)
min(𝐸) (21)
The selection of algorithms for a given problem 𝐽𝑆𝑃 in-
volves identifying the most appropriate algorithm from a The maximum energy consumption (Equation 19) indi-
collection capable of solving 𝐽𝑆𝑃 , taking into account the cates the highest energy required for any single operation.
specific characteristics of 𝐽𝑆𝑃 . Rubinoff [13] formalized The mean energy consumption (Equation 20) provides the
this process of algorithm selection. Rubinoff defined key average energy used across all operations, reflecting the
elements, including the problem space 𝑋, representing all overall energy profile. The minimum energy consumption
instances of 𝐽𝑆𝑃 ; the algorithm space 𝐴, encompassing (Equation 21) shows the lowest energy usage for an opera-
algorithms capable of solving any 𝑗𝑠𝑝 ∈ 𝑋; and a perfor- tion, highlighting the least energy-intensive job segment.
mance metric 𝑦, which quantifies algorithm effectiveness (︃ )︃
for solving 𝑗𝑠𝑝 ∈ 𝑋.
∑︁ ∑︁
max(𝑃𝑗𝑚𝑠 ) (22)
The core objective is to establish a function 𝑆 : 𝑋 → 𝑗∈𝐽 𝑚∈𝑀
𝑠∈𝑆
𝐴 that, for each problem instance 𝑗𝑠𝑝 ∈ 𝑋, selects the
optimal algorithm from 𝐴 based on metric 𝑦. To effectively Maximum makespan (Equation 22) represents the maxi-
characterize each 𝑗𝑠𝑝, a feature set 𝐹 is constructed to mum makespan of the instance obtained, assuming that all
represent 𝑝 and assist in the decision-making process for operations are performed serially with their maximum pro-
𝑆. Consequently, 𝑆 is defined as a composite function 𝑆 = cessing time. This value gives the longest possible duration
𝑇 ∘ 𝐺, where 𝐺 : 𝑋 → R|𝐹 | maps 𝑝 to its feature vector to complete all jobs, assuming no parallel processing.
in R|𝐹 | , and 𝑇 : R|𝐹 | → 𝐴 selects the algorithm from 𝐴 (︃ )︃
based on this feature representation. The choice of 𝐹 is
∑︁
max min(𝑃𝑗𝑚𝑠 ) (23)
critical as it must be informative and accurately represent 𝑗∈𝐽
𝑚∈𝑀
𝑠∈𝑆
the characteristics of 𝐽𝑆𝑃 .
Minimum makespan (Equation 23) represents the
Considering the modeling of algorithm selectors in Figure
makespan of the solution obtained by considering that the
1, an algorithm selector structure is proposed, where it can
operations can be performed in parallel and do not overlap.
be seen that it is composed of a training phase, in which
This makespan represents a lower bound of the possible
the features of a set of instances are processed to generate
makespan in a solution, indicating the shortest time to com-
a set of data and are solved using three solvers: GECODE,
plete all jobs if perfectly parallelized.
CPLEX, and GUROBI. Once the instances have been solved,
the extracted features are related to the best algorithm that (︃ )︃
has solved that instance, and different machine learning
∑︁ ∑︁
max(𝐸𝑗𝑚𝑠 ) (24)
𝑠∈𝑆
models are trained in order to validate which is the one 𝑚∈𝑀 𝑗∈𝐽
that obtains the best accuracy and thus use it to recommend (︃ )︃
future instances.
∑︁ ∑︁
min(𝐸𝑗𝑚𝑠 ) (25)
The following subsections detail each of the training pro- 𝑚∈𝑀 𝑗∈𝐽
𝑠∈𝑆
cesses.
The sum of the maximum (Equation 24) and minimum
(Equation 25) energy consumption is obtained by adding
3.1. Feature processing for each operation its maximum and minimum energy con-
For each instance, we extract the typical characteristics of a sumption, respectively. These values provide insights into
JSP (Job Shop Scheduling) problem, such as the number of the total energy requirements of the job set under extreme
jobs |𝐽|, the number of machines |𝑀 |, the type of Release conditions.
date, and Due date constraint 𝑅𝑑/𝐷𝑑, and the number of ⎧
speeds |𝑆|. Additionally, we extract other features that are ⎨−1 (︃
⎪ )︃ 𝑅𝑑/𝐷𝑑 = 0
obtained in a less direct manner and aim to be as informa- ∑︁ ∑︁ (26)
⎪ max(𝑃𝑗𝑚𝑠 ) 𝑅𝑑/𝐷𝑑 = 1
⎩ 𝑠∈𝑆
𝑗∈𝐽 𝑚∈𝑀
Figure 1: Structure of the proposed recommender system.
⎧
⎪
⎪−1 𝑅𝑑/𝐷𝑑 = 0
⎪
⎪
⎪
⎪
⎪
⎪
⎪ ∑︁ max(0, min(𝐷𝑑𝑗 , 𝐷𝑑𝑗 ) − max(𝑅𝑑𝑗 , 𝑅𝑑𝑗 ))
⎪
⎪ 1 2 1 2
⎪
⎪
⎪ 𝐷𝑑𝑗1 − 𝑅𝑑𝑗1
⎨ 𝑗1𝑗 ,𝑗̸=2𝑗∈𝐽
⎪
⎪
(28)
1 2
|𝐽|·(|𝐽|−1)
𝑅𝑑/𝐷𝑑 = 1
⎪
⎪
⎪
⎪
⎪
⎪
⎪ ∑︁ ∑︁ max(0, min(𝐷𝑑𝑗 𝑚 , 𝐷𝑑𝑗 𝑚 ) − max(𝑅𝑑𝑗 𝑚 , 𝑅𝑑𝑗 𝑚 ))
⎪
⎪ 1 2 1 2
⎪
⎪
⎪ 𝐷𝑑𝑗1 𝑚 − 𝑅𝑑𝑗1 𝑚
⎪
⎪ 𝑗1 ,𝑗2 ∈𝐽 𝑚∈𝑀
⎩ 𝑗1 ̸=𝑗2
⎪
⎪
|𝐽|·(|𝐽|−1)·|𝑀 |
𝑅𝑑/𝐷𝑑 = 2
Maximum Tardiness (Equation 26) represents the max- jobs or operations coincide, which impacts the complexity
imum possible delay in a solution. If there are no release and difficulty of scheduling.
or due date constraints (𝑅𝑑/𝐷𝑑 = 0), it is set to -1. Other-
wise, it sums the maximum processing times, indicating the 3.2. Machine Learning Models
worst-case delay scenario.
Once the instances have been vectorized and solved, a tabu-
⎧ lar data set is constructed with the characteristics of each
⎪−1
⎪
⎪
𝑅𝑑/𝐷𝑑 = 0 instance and the solver that has found the best solution,
that is, the one that has obtained the lowest value of the
⎪
⎪
⎪
⎪
∑︁ 𝐷𝑑𝑗 − 𝑅𝑑𝑗 objective function.
⎪
⎪
⎪
⎪
This dataset has been separated into two subsets, a train-
⎪ ∑︀
𝑚∈𝑀 𝑃𝑗𝑚
⎪
⎨
𝑗∈𝐽
|𝐽|
𝑅𝑑/𝐷𝑑 = 1 (27) ing subset with a size of 80% and a test subset with the
remaining 20%. In addition, it has been ensured that the
⎪
⎪
⎪
⎪
same number in proportion of instances exists in the two
⎪
⎪ ∑︁ ∑︁ 𝐷𝑑𝑗𝑚 − 𝑅𝑑𝑗𝑚
⎪
⎪
subsets.
⎪
𝑃𝑗𝑚
⎪
⎪
⎪
⎩ 𝑗∈𝐽 𝑚∈𝑀
⎪
𝑅𝑑/𝐷𝑑 = 2 The training dataset has been used to validate different
|𝐽|·|𝑀 |
models using five-fold cross-validation. The validated mod-
Time-Window (Equation 27) represents the number of els are the following:
times a job or operation can be performed within its time
window. This metric varies based on the type of release and • Logistic Regression: This is a statistical method for
due date constraints: no constraints, job-level constraints, or analyzing a dataset in which one or more indepen-
operation-level constraints, indicating flexibility in schedul- dent variables determine an outcome. The outcome
ing. is measured with a dichotomous variable (i.e., two
Overlap (Equation 28) represents the degree of overlap be- possible outcomes). Logistic regression is particu-
tween the time windows of the jobs or operations. This met- larly useful for binary classification problems and
ric assesses how much the scheduling windows for different
provides insights into the relationships between the time, optimum, satisfaction rate, and the number of un-
variables and the probability of the outcomes. solved solutions, are presented above.
• Decision Tree: This is a decision support tool that
uses a tree-like model of decisions and their possi- 4.1. Instances
ble consequences, including chance event outcomes,
resource costs, and utility. A decision tree is built by Instance creation is one of the most important aspects of
splitting the dataset into subsets based on the value evaluation as it allows a specific number of instances to be
of input features, with the goal of making the most configured to ensure the most comprehensive evaluation
informative splits. This method is easy to interpret possible, taking into account all possible combinations the
and visualize, making it useful for understanding problem may encounter in real-life scenarios.
the structure of the data. The JSP Benchmark used for testing is composed of the
• Gaussian Naive Bayes: This is a probabilistic classi- number of jobs (𝐽) and machines (𝑀 ) to determine each
fier based on Bayes’ theorem, with the assumption job’s tasks. These variables can take any natural number.
that the features are independent given the class In this test set, the set {5, 10, 20, 25, 50, 100} is considered
label and that they follow a Gaussian distribution. for 𝐽. The release and due date can take values {0, 1, 2},
Despite its simplicity, Gaussian Naive Bayes can per- speed scaling can take values {1, 3, 5}, and statistical distri-
form well in various situations, especially when the butions considered are {uniform, normal, exponential}. For
assumption of independence roughly holds true. each configuration, 10 instances are generated with different
• K-Nearest Neighbors (KNN): This is a non- seeds to ensure substantial variation between them. There-
parametric method used for classification and re- fore, a total of 6(𝐽) × 6(𝑀 ) × 3(𝑟𝑑𝑑𝑑) × 3(𝑠𝑠) × 3(𝑑𝑖𝑠𝑡) ×
gression. For classification, the input consists of 10(𝑄) = 9720 instances are obtained.
the 𝑘 closest training examples in the feature space,
and the output is a class membership. The object
is assigned to the class most common among its 𝑘
nearest neighbors.
• Random Forest: This is an ensemble learning method
for classification and regression that constructs mul-
tiple decision trees during training and outputs the
mode of the classes (classification) or mean predic-
tion (regression) of the individual trees. Random
forests improve the predictive accuracy and control
over-fitting by averaging multiple trees, reducing
the model’s variance.
• XGBoost [14]: This is an optimized distributed gradi-
ent boosting library designed to be highly efficient,
flexible, and portable. It implements machine learn-
ing algorithms under the gradient boosting frame- Figure 2: Distribution of timeout and relationship between time
work, which builds models in a stage-wise fashion and energy.
and generalizes them by optimizing for a differen-
tiable loss function. XGBoost is known for its speed
The time allocated for resolving each instance depends
and performance, making it a popular choice for
on the specific characteristics of the problem. An example
structured/tabular data.
of this allocation is illustrated in Figure 2. In this exam-
• Multi-Layer Perceptron (MLP): This is a class of feed- ple, an instance with 50 jobs, 10 machines, no Release Date
forward artificial neural networks that consist of at or Due Date, and a single speed per machine is allocated
least three layers of nodes: an input layer, a hid- 149 seconds. The principle is that if the maximum allo-
den layer, and an output layer. Except for the input cation time for an instance is 300,000 milliseconds, each
nodes, each node (or neuron) uses a nonlinear activa- characteristic’s impact on the allocation should be equiv-
tion function. MLPs are capable of learning complex alent. Therefore, each characteristic contributes at most
mappings from inputs to outputs and are trained 300, 000/4 = 75, 000 milliseconds. In this manner, for the
using backpropagation. given example, if the Release Date and Due Date are as-
signed at the operation level (RDDD = 2), they contribute
4. Evaluation 75,000 milliseconds. If they are absent (RDDD = 0), they
contribute 50 milliseconds. When assigned at the job level,
All experiments were conducted on a system equipped with the contribution is determined by exponential interpolation
an Intel 3.60 GHz 12th generation Core i7 CPU and 64 GB between these two cases.
of RAM. The implementation was developed in Python 3.11.
Well-known solvers such as GUROBI [15], CPLEX [16], and 4.2. Results
GECODE [17], which are implemented on Minizinc, were
utilized. Upon defining the problem instances and setting appropriate
To evaluate the quality of the solutions obtained, the search time limits for each solver, the focus shifted toward
mono-objective function shown in Equation 11 is used to analyzing and interpreting the outcomes. This involved
compare the best solutions from the solvers. Other impor- evaluating the efficacy of the solvers employed, assessing
tant results, such as the average objective function, solving solution quality, and considering the broader implications
within the problem domain.
tain medium-sized setups but faces scalability challenges.
GECODE shines in complex problems, offering robust scal-
ability and reliability despite occasional computational hur-
dles. These findings aid practitioners in optimizing solver
choices and considering trade-offs between solution quality,
efficiency, and problem complexity.
4.3. Complexity analysis
Observing the results obtained by the methods used, a rela-
tionship is observed between the parameters employed and
the complexity of the instances. This part of the study fo-
cuses on the in-depth analysis of each parameter to observe
its contribution to the overall complexity of the instances.
Figure 3: Quantity of optimum, satisfied and unresolved in-
stances by each solver.
Figure 3 illustrates the distribution of solved instances
among GUROBI, CPLEX, and GECODE across three cate-
gories: optimal (best solution), satisfied (feasible but not
optimal), and unresolved (not solved).
GUROBI emerged as the top performer overall, solv-
ing the highest number of optimal solutions and consis-
tently demonstrating its ability to find acceptable solutions
even when optimal ones were unfeasible. This underscores
GUROBI’s robust capability in efficiently managing a di-
verse array of problem types. Conversely, GECODE excelled (a) by number of machines
in finding feasible solutions, significantly outperforming
other solvers in achieving satisfactory solutions. Moreover,
GECODE showed the fewest instances left unresolved, high-
lighting its reliability in tackling complex problems without
abandoning them.
In contrast, CPLEX, while proficient, faced challenges
with more complex problem instances, leading to a higher
incidence of unresolved cases. Although it achieved rea-
sonable numbers of optimal and satisfactory solutions, its
performance consistency was observed to be less reliable
compared to GUROBI and GECODE.
Table 1 compares solution times and objective function
values from GUROBI, CPLEX, and GECODE across differ-
ent job and machine configurations. This analysis reveals (b) by number of jobs
insights into each solver’s performance characteristics, high-
lighting strengths and limitations in solving optimization Figure 4: Number of instances solved
problems.
For 5 to 20 jobs, GUROBI consistently shows shorter so-
To delve deeper into the data presented in Table 1, Fig-
lution times and competitive objective values compared to
ure 4 provides a general overview of the number of solved
CPLEX and GECODE. Its efficiency and precision make it
instances. Organizing the data by the number of machines,
highly effective in simpler problem instances.
as shown in subfigure 4a, it is evident that as the number of
In medium-sized scenarios (20 to 50 jobs), GUROBI main-
machines increases, the number of solved instances progres-
tains an edge, particularly with fewer machines, though
sively decreases except for the case of 5 machines, where
CPLEX occasionally performs better in specific configura-
all instances are solved for all possible job configurations.
tions. GUROBI generally achieves superior objective func-
Looking at subfigure 4b, which is organized by the number
tion values in varied problem setups.
of jobs for all possible machine configurations, it can be
In complex cases (50 to 100 jobs), GECODE demonstrates
seen that all instances are solved for 5 and 10 jobs, but there
exceptional scalability despite encountering timeouts in
is a notable decrease for the rest. Focusing on the set of 20
some instances. GUROBI and CPLEX struggle more often
and 25 jobs, it can be observed that there is a slight decrease
with timeouts as problem size and complexity increase, yet
from 25 machines onwards; later, the reasons for this are
GUROBI often maintains competitive objective values.
analyzed. For instances with 50 and 100 jobs, the decrease
These insights underscore the importance of selecting
in the number of solved instances is exponential. Only all
solvers based on problem specifics. GUROBI excels in
instances are solved for a configuration of 5 machines for
smaller to medium-sized instances, balancing efficiency
100 jobs and 5 and 10 machines for 50 jobs. This figure
and high-quality solutions. CPLEX performs well in cer-
Solve Time Objective
Jobs Machines
GUROBI CPLEX Gecode GUROBI CPLEX Gecode
5 6499.47 9393.54 76754.74 0.58053 0.57924 0.7748
10 22177.73 35193.18 77122.47 0.46884 0.46842 0.64781
20 50222.29 57898.63 81637.16 0.42377 0.42422 0.58867
5
25 55920.19 59732.08 79771.76 0.41208 0.41279 0.5677
50 69226.88 71453.81 95645.56 0.39632 0.40691 0.53307
100 110177.22 123730.15 154180.72 0.38944 0.42882 0.51176
5 72263.13 76261.31 85388.49 0.56284 0.56433 0.77965
10 69831.23 71671.93 86539.69 0.44524 0.4482 0.64365
20 71619.72 74610.4 89860.43 0.38908 0.39532 0.5713
10
25 73930.71 78202.9 91969.19 0.3798 0.39247 0.54207
50 89935.3 95355.06 109638.51 0.36431 0.38019 0.49456
100 146282.37 152079.82 168202.69 0.35029 0.30281 0.35159
5 80190.01 88650.74 89079.98 0.65727 0.67151 0.83772
10 80369.98 89368.09 89895.89 0.48249 0.48393 0.71326
20 91070.63 83648.86 92953.44 0.40615 0.36374 0.60325
20
25 92555.52 86596.51 96516.25 0.38184 0.3135 0.58104
50 109441.69 97752.14 78306.1 0.35987 0.24087 0.20729
100 164169.07 161843.67 112923.84 0.29168 0.06245 0.00733
5 73156.78 86322.15 91381.59 0.64018 0.63401 0.84305
10 78504.99 83658.47 92142.26 0.57263 0.46831 0.73123
20 99400.75 83989.35 95774.25 0.46229 0.36985 0.62663
25
25 104469.18 76519.47 102202.35 0.42563 0.30161 0.61462
50 118524.24 127129.68 59800.26 0.31818 0.21552 0.13974
100 168354.77 Timeout 113885.23 0.28319 Timeout 0.01021
5 101811.91 86469.46 110038.97 0.70258 0.49251 0.86043
10 115365.19 71684.29 110542.27 0.56627 0.21168 0.75717
20 108631.5 117752.67 78930.63 0.37003 0.12673 0.66168
50
25 105251.06 120220 72639.27 0.43698 0.16123 0.57382
50 136252.05 Timeout 59343.32 0.47363 Timeout 0.14455
100 153826.43 Timeout 122941.2 0.91743 Timeout 0.04168
5 Timeout 114685.56 183151.94 Timeout 0.32913 0.86754
10 Timeout Timeout 180057.66 Timeout Timeout 0.77187
20 Timeout Timeout 139246.52 Timeout Timeout 0.68049
100
25 Timeout Timeout 122740.76 Timeout Timeout 0.59173
50 Timeout Timeout 116506.13 Timeout Timeout 0.4602
100 Timeout Timeout 157021.85 Timeout Timeout 0.13594
Table 1
Comparison of mean resolution time and mean objective function obtained with different solvers.
illustrates how the number of jobs and machines affects the unseen data. The high accuracy suggests that XGBoost’s
possibility of obtaining a solution to the problem at hand. ensemble learning approach, which combines multiple de-
cision trees to improve performance, is particularly well-
4.4. Algorithm selector results suited to this dataset. Moreover, the performance difference
between XGBoost and other models like Random Forest and
MLP, which also showed strong results,
Model Accuracy (%)
Logistic Regression 76.08
Gaussian Naive Bayes 48.93
Decision Tree 79.48
𝐾 -Nearest Neighbors 78.34
Random Forest 82.87
XGBoost 83.26
MLP 82.81
Table 2
Table showing the training results of the different models
Figure 5: Confusion matrix for the algorithm selector predictions
(true algorithms on the y-axis, predicted algorithms on the x-axis).
Table 2 shows the validation results of the tested models.
As can be seen, XGBoost is the model with the best valida-
tion accuracy. Training this model with the total training The confusion matrix in Figure 5 presents the algorithm
data set and testing it with the test set finally yields an accu- selector’s classification results. Each cell value represents
racy of 84.51%. This indicates that XGBoost performs well the number of instances where the algorithm selector pre-
during the validation phase and generalizes effectively to dicted the algorithm in the corresponding column for a
problem best solved by the algorithm in the corresponding racy across a broader range of JSP scenarios. Advancements
row. For instance, the selector correctly identified GUROBI in solver performance under varying constraints promise
for 611 out of the total instances where GUROBI was the to expand the practical utility of scheduling optimization
best choice. Similarly, GECODE was correctly identified 396 tools in real-world manufacturing settings, emphasizing
times. However, there are misclassifications, such as pre- efficiency and sustainability.
dicting GUROBI when CPLEX was optimal, which occurred Although the results obtained are not as high as those
70 times. reported in the literature, it should be noted that the energy-
An in-depth analysis of the precision and recall metrics aware JSP constitutes a more complex problem compared
provides further insights into the performance of the al- to the standard JSP and flexible JSP found in the literature.
gorithm selector. GECODE achieved a precision of 90.20%, Furthermore, this study uses a smaller set of features than
indicating that 90.20% of the instances predicted as GECODE those used in other studies, yet the accuracy achieved is not
were correctly identified. Its recall was 86.84%, signifying significantly lower.
that 86.84% of the actual GECODE instances were correctly In conclusion, this work advances both academic under-
detected. This high precision and recall demonstrate the standing and practical applications by integrating traditional
algorithm selector’s robustness in identifying GECODE in- optimization techniques with modern machine-learning ap-
stances accurately. proaches. It offers tools that can significantly benefit re-
On the other hand, CPLEX showed a precision of 62.76%, search and industrial practices, addressing contemporary
meaning that only 62.76% of the predictions for CPLEX were challenges in operations management and manufacturing
accurate, and a recall of 73.75%, which indicates that 73.75% logistics.
of the actual CPLEX instances were correctly classified. The
lower precision for CPLEX suggests a higher rate of false
positives, which could imply that the algorithm selector References
often misclassifies other algorithms as CPLEX.
[1] H. Xiong, S. Shi, D. Ren, J. Hu, A survey
For GUROBI, the precision was 89.85%, reflecting that
of job shop scheduling problem: The types and
89.85% of the GUROBI predictions were correct, and the
models, Computers & Operations Research 142
recall was 86.66%, meaning that 86.66% of the actual GUROBI
(2022) 105731. doi:https://doi.org/10.1016/j.
instances were identified correctly. These values indicate a
cor.2022.105731.
strong performance, similar to GECODE, highlighting the
[2] D. B. M. M. Fontes, S. M. Homayouni, J. F. Gonçalves,
selector’s efficiency in recognizing GUROBI accurately.
A hybrid particle swarm optimization and simulated
These metrics, precision, and recall, are crucial for eval-
annealing algorithm for the job shop scheduling prob-
uating the algorithm selector’s effectiveness, as they pro-
lem with transport resources, European Journal of Op-
vide a more comprehensive understanding of its perfor-
erational Research 306 (2023) 1140–1157. doi:https:
mance beyond simple accuracy. They highlight the selec-
//doi.org/10.1016/j.ejor.2022.09.006.
tor’s strengths in accurately identifying certain algorithms
[3] D. M. Torres, F. Barber, M. A. Salido, Psplib-
while also pointing out areas where misclassification occurs,
energy: a extension of psplib library to assess the
thus providing a clear direction for further improvements.
energy optimization in the rcpsp, Inteligencia
Artificial 17 (2014) 48–61. doi:10.4114/intartif.
5. Conclusions vol17iss54pp48-61.
[4] M. M. S. El-Kholany, M. Gebser, K. Schekotihin, Prob-
This study explores the complexities of JSP, emphasizing lem decomposition and multi-shot asp solving for job-
its NP-completeness and diverse optimization goals such as shop scheduling, 2022.
makespan, energy consumption, and tardiness. The prob- [5] C. Perez, M. A. Salido, D. Gurrea, A metaheuristic
lem presents significant computational challenges due to search technique for solving the warehouse stock man-
its combinatorial nature, making timely optimal solutions agement problem and the routing problem in a real
crucial in operations research and manufacturing. company, in: Artificial Intelligence XXXVII, Springer
An innovative aspect of this research is integrating ma- International Publishing, Cham, 2020, pp. 187–201.
chine learning techniques to enhance algorithm selection [6] M. Dai, D. Tang, A. Giret, M. A. Salido, Multi-objective
for JSP instances. By extracting comprehensive features like optimization for energy-efficient flexible job shop
job and machine characteristics, release dates, and energy scheduling problem with transportation constraints,
requirements, models such as XGBoost and Random Forest Robotics and Computer-Integrated Manufacturing 59
were effectively trained. These models accurately recom- (2019) 143–157. doi:https://doi.org/10.1016/j.
mend suitable solvers like GUROBI, CPLEX, and GECODE, rcim.2019.04.006.
streamlining decision-making for solving diverse and com- [7] C. Pérez, L. Climent, G. Nicoló, A. Arbelaez, M. A.
plex scheduling problems. Salido, A hybrid metaheuristic with learning for
GUROBI proved particularly efficient for smaller to a real supply chain scheduling problem, Engi-
medium-sized instances, consistently delivering optimal neering Applications of Artificial Intelligence 126
and satisfactory solutions across different configurations. (2023) 107188. doi:https://doi.org/10.1016/j.
Meanwhile, GECODE demonstrated robust scalability, ex- engappai.2023.107188.
celling in complex scenarios despite occasional computa- [8] M. A. Salido, J. Escamilla, A. Giret, F. Barber,
tional challenges. This analysis underscores the importance A genetic algorithm for energy-efficiency in job-
of selecting solvers based on specific problem parameters shop scheduling, Int J Adv Manuf Technol 85
to optimize solution quality and computational efficiency. (2016) 1303–1314. doi:https://doi.org/10.1007/
Looking ahead, the study suggests refining feature extrac- s00170-015-7987-0.
tion methodologies to enhance the algorithm selector’s accu- [9] K. Jyothi, R. B. Dubey, Minimizing non-processing en-
ergy consumption/total weighted tardiness & ear-
liness, and makespan into typical production schedul-
ing model-the job shop scheduling problem, Journal
of Intelligent & Fuzzy Systems 45 (2023) 6959–6981.
doi:10.3233/JIFS-222362.
[10] A. Ham, M.-J. Park, K. M. Kim, Energy-aware flexible
job shop scheduling using mixed integer programming
and constraint programming, Mathematical Problems
in Engineering 2021 (2021) 1–12. doi:10.1155/2021/
8035806.
[11] D. Müller, M. G. Müller, D. Kress, E. Pesch,
An algorithm selection approach for the flexi-
ble job shop scheduling problem: Choosing con-
straint programming solvers through machine learn-
ing, European Journal of Operational Research 302
(2022) 874–891. doi:https://doi.org/10.1016/j.
ejor.2022.01.034.
[12] S. Strassl, N. Musliu, Instance space analysis and
algorithm selection for the job shop scheduling
problem, Computers & Operations Research 141
(2022) 105661. doi:https://doi.org/10.1016/j.
cor.2021.105661.
[13] J. R. Rice, The algorithm selection problem. this work
was partially supported by the national science foun-
dation through grant gp-32940x. this chapter was
presented as the george e. forsythe memorial lec-
ture at the computer science conference, february 19,
1975, washington, d. c., in: Advances in Comput-
ers, volume 15 of Advances in Computers, Elsevier,
1976, pp. 65–118. doi:https://doi.org/10.1016/
S0065-2458(08)60520-3.
[14] T. Chen, C. Guestrin, Xgboost: A scalable tree boosting
system, in: Proceedings of the 22nd ACM SIGKDD
International Conference on Knowledge Discovery
and Data Mining, KDD ’16, ACM, 2022, p. 785–794.
doi:10.1145/2939672.2939785.
[15] Y. Zeiträg, J. Rui Figueira, G. Figueira, A coopera-
tive coevolutionary hyper-heuristic approach to solve
lot-sizing and job shop scheduling problems using ge-
netic programming, International Journal of Produc-
tion Research (2024). doi:10.1080/00207543.2023.
2301044.
[16] D. Rooyani, F. M. Defersha, An efficient two-stage ge-
netic algorithm for flexible job-shop scheduling, IFAC-
PapersOnLine 52 (2019). doi:10.1016/j.ifacol.
2019.11.585.
[17] L. Ingmar, C. Schulte, Making compact-table com-
pact, in: Principles and Practice of Constraint Pro-
gramming, Springer International Publishing, Cham,
2018, pp. 210–218.