=Paper=
{{Paper
|id=Vol-3812/paper7
|storemode=property
|title=Instance Configuration for Sustainable Job Shop Scheduling
|pdfUrl=https://ceur-ws.org/Vol-3812/paper7.pdf
|volume=Vol-3812
|authors=Christian Perez,Carlos March,Miguel A. Salido
|dblpUrl=https://dblp.org/rec/conf/confws/PerezMS24
}}
==Instance Configuration for Sustainable Job Shop Scheduling==
https://ceur-ws.org/Vol-3812/paper7.pdf
Instance Configuration for Sustainable Job Shop Scheduling
Christian Pérez1,2,*,† , Carlos March1,† 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 a pivotal challenge in operations research and is essential for evaluating the effec-
tiveness and performance of scheduling algorithms. Scheduling problems are a crucial domain in combinatorial optimization,
where resources (machines) are allocated to job tasks to minimize the completion time (makespan) alongside other objectives
like energy consumption. This research delves into the intricacies of JSP, focusing on optimizing performance metrics and
minimizing energy consumption while considering various constraints such as deadlines and release dates. Recognizing the
multi-dimensional nature of benchmarking in JSP, this study underscores the significance of reference libraries and datasets
like JSPLIB in enriching algorithm evaluation. The research highlights the importance of problem instance characteristics,
including job and machine numbers, processing times, and machine availability, emphasizing the complexities introduced by
energy consumption considerations.
An innovative instance configurator is proposed, equipped with parameters such as the number of jobs, machines, tasks,
and speeds, alongside distributions for processing times and energy consumption. The generated instances encompass
various configurations, reflecting real-world scenarios and operational constraints. These instances facilitate comprehensive
benchmarking and evaluation of scheduling algorithms, particularly in contexts of energy efficiency. A comprehensive set of
500 test instances has been generated and made publicly available, promoting further research and benchmarking in JSP.
These instances enable robust analyses and foster collaboration in developing advanced, energy-efficient scheduling solutions
by providing diverse scenarios.
Keywords
Job Shop Scheduling Problem, Instance Generation, Benchmarking, Energy consumption, Speed scaling
1. Introduction from seminal works and experimental studies, thereby
enriching the evaluation of algorithms [3].
The Job Shop Scheduling Problem (JSP) stands as a cor- A profound understanding of problem instance char-
nerstone in the realm of operations research and opti- acteristics significantly shapes benchmarking efforts in
mization, representing a fundamental challenge pivotal JSP. Factors such as the number of jobs and machines,
for evaluating algorithmic effectiveness and performance. variability in processing times, machine availability, and
In essence, JSP revolves around the intricate task of al- precedence relationships exert notable influences on al-
locating jobs to machines within a manufacturing en- gorithm performance [4]. Furthermore, incorporating
vironment to optimize a plethora of performance met- energy consumption considerations, contingent upon
rics, ranging from makespan and flow time to tardiness, machine speed and operational attributes, introduces an
resource utilization, and energy consumption [1]. The added layer of complexity to these instances [5]. The del-
process of benchmarking in JSP is multi-dimensional, ne- icate balance between energy consumption and schedul-
cessitating the definition and evaluation of metrics such ing decisions emerges as paramount in achieving energy
as makespan, energy consumption, and tardiness to as- efficiency goals without compromising production tar-
sess scheduling efficiency and resource utilization [2]. gets [6].
Reference libraries and datasets like JSPLIB play an in- In recent years, the spotlight on addressing energy ef-
dispensable role in these benchmarking endeavours, fur- ficiency within the realm of JSP has intensified, driven by
nishing researchers with a rich array of instances sourced its profound environmental and economic implications
[7]. Strategies involving integrating speed-adjustable
ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, machines and vehicles have been explored as avenues
2024, Girona, Spain
*
Corresponding author. to optimize energy consumption while upholding pro-
†
These authors contributed equally. ductivity levels [8]. Concurrently, developing advanced
$ cripeber@upv.es (C. Pérez); cmarmoy@upv.es (C. March); algorithms and optimization techniques tailored to tackle
msalido@upv.es (M. Salido) energy-related challenges has seen significant advance-
https://gps.blogs.upv.es/ (C. Pérez); https://gps.blogs.upv.es/ ments, considering factors such as machine speed, idle
(C. March); https://gps.blogs.upv.es/ (M. Salido) time, and energy requirements [9]. Real-world implemen-
0000-0002-9121-7939 (C. Pérez); 0009-0009-7525-9133
(C. March); 0000-0002-4835-4057 (M. Salido)
tations of these energy-efficient strategies have yielded
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License tangible benefits, manifesting in substantial cost savings
Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
and positive environmental impacts [10]. Algorithm 1 Instance Configurator
In conclusion, the imperative of energy efficiency in input: Quantity of instances 𝑄, Number of machines
JSP research has become increasingly pronounced, paral- 𝑀 , Number of jobs 𝐽, Number of tasks 𝑇 , Release and
leling the traditional focus on performance metrics [11]. due date type 𝑟𝑟𝑑𝑑, Random seed 𝑠𝑒𝑒𝑑, Distribution 𝑑𝑖𝑠𝑡
Benchmarking is a linchpin in evaluating the efficacy output: Generated instances 𝐺
of energy-efficient scheduling strategies, furnishing in- 1: 𝑆𝑒𝑡𝑆𝑒𝑒𝑑(𝑠𝑒𝑒𝑑)
valuable insights into their ramifications on production 2: 𝐺 ← [ ]
efficiency and energy consumption [12]. Manufacturers 3: for 𝑞 from 1 to 𝑄 do
can embark toward more sustainable and economically 4: 𝑂 ← 𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝐽𝑜𝑏𝑠𝑂𝑝𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠(𝑇, 𝐽, 𝑀 )
viable operations by harnessing advanced optimization 5: 𝑃 ← 𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑃 𝑟𝑜𝑐𝑒𝑠𝑠𝑖𝑛𝑔𝑇 𝑖𝑚𝑒𝑠(𝐽, 𝑀, 𝑆)
techniques and leveraging real-world implementations. 6: 𝐸 ← 𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝐸𝑛𝑒𝑟𝑔𝑦(𝐽, 𝑀, 𝑆)
7: 𝑅, 𝐷 ← 𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑒𝑅𝐷𝐷𝑎𝑡𝑒(𝐽, 𝑀, 𝑑𝑖𝑠𝑡)
8: 𝐺 ← 𝐺 ∪ 𝐽𝑆𝑃 (𝑂, 𝑃, 𝐸, 𝑅, 𝐷)
2. Instance Configuration 9: end for
Test sets play a vital role in JSP research by providing 10: return 𝐺
a standardized platform for comparing algorithmic ap-
proaches. Their diversity enables researchers to evaluate
various algorithms, from heuristics to exact methods, algorithm generates jobs and tasks within a loop iterating
identifying strengths, weaknesses, and potential limi- through each instance 𝑞 from 0 to 𝑄 − 1 (Line 4).
tations across different contexts [13]. However, as in- Next, each job operation’s processing times and energy
dustrial systems evolve, the complexity of real-world consumption are generated.
problems increases, necessitating the development or 𝑥
𝑓 (𝑥) = ⌊𝑒− 100 × 100⌋ (1)
expansion of test sets to simulate real-world scenarios
better.
To address this need, the proposed instance configura- log(2)
𝑔(𝑥) = 4.0704 × (2)
tor operates with the following parameters: log(1 + (𝑥 × 2.5093)3 )
• 𝐽 = {0, . . . , 𝑛}: the set of jobs. The functions responsible for generating the process-
ing times (line 5) and energy consumption (line 6) for the
• 𝑀 = {0, . . . , 𝑚}: the set of machines. combination of jobs, machines, and speeds are managed
by functions 𝑓 (𝑥) 1 and 𝑔(𝑥) 2, as illustrated in Figure 1
• 𝑆 = {0, . . . , 𝑠}: the set of speeds, indexed by 𝑠 in 𝑆.
as studied in [14]. These functions balance the variables
• 𝑇𝑗 : the set of tasks in job 𝑗, indexed by 𝑡𝑗𝑡 ∈ 𝑇𝑗 , ∀𝑗 ∈ to establish a correlation between processing time and
𝐽, ∀𝑡 ∈ 𝑀 . energy consumption. In these equations, 𝑥 represents the
processing time for Equation 𝑓 (𝑥) 1 and the energy con-
• 𝐷𝑗𝑡 : the due date of task job 𝑡𝑗𝑡 ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑀 . sumption for Equation 𝑔(𝑥) 2. Speeds are generated by
obtaining the energy consumption percentage for each
• 𝑅𝑗𝑡 : the release date of task job 𝑡𝑗𝑡 ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑀 .
speed using Equation 𝑓 (𝑥) 1, which models an inverse
• 𝑃𝑗𝑡𝑠 : the processing time of task job 𝑡𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ relationship between processing time and energy con-
𝑀, ∀𝑠 ∈ 𝑆. sumption. This involves dividing the interval [0.5, 3] into
|𝑆| − 1 equal parts, where the boundaries of these new
• 𝐸𝑗𝑡𝑠 : the energy consumption for processing task job intervals correspond to the energy consumption percent-
𝑡𝑗𝑡 , ∀𝑗 ∈ 𝐽, ∀𝑡 ∈ 𝑀, ∀𝑠 ∈ 𝑆. ages for each speed. Subsequently, Equation 𝑔(𝑥) 2 is
utilized to determine the fraction of time corresponding
The process of configuring instances, managed by Al- to each speed.
gorithm 1, is initiated by receiving several input parame- Release and due dates are computed using functions
ters: the number of instances to generate 𝑄, the number based on the chosen distribution (Line 7). Each distri-
of machines 𝑀 , the count of jobs 𝐽, the number of tasks bution offers distinct characteristics suited for modeling
𝑡, the types of release and due dates 𝑟𝑟𝑑𝑑, random seeds various real-world scenarios.
𝑠𝑒𝑒𝑑𝑠, and the distribution 𝑑𝑖𝑠𝑡. The exponential distribution, defined by its probability
Subsequently, the algorithm executes a series of steps density function 𝑓 (𝑥; 𝜆) = 𝜆𝑒−𝜆𝑥 , is ideal for modeling
to generate instances systematically. The random seed is the time until an event occurs, such as machine failures or
initialized to ensure reproducibility, and an empty list 𝐺 job arrivals, assuming a constant hazard rate 𝜆 > 0. Its
is created to store the generated instances (Line 2). The mean is 1 . The Gaussian distribution, with mean 𝜇 and
𝜆
standard deviation 𝜎, has a probability density function
Figure 1: Distribution of processing times and the relationship between time and energy
(𝑥−𝜇)2
−
𝑓 (𝑥; 𝜇, 𝜎) = 𝜎√12𝜋 𝑒 2𝜎2 . This distribution repre- ing identical data but with different operational speeds.
sents naturally occurring variations in processing times Specifically, two additional instances were derived from
or delays. The uniform distribution generates values each original: one incorporating the first, third, and fifth-
evenly within a specified range, defined by the proba- speed scaling and another utilizing only the third-speed
bility density function 𝑓 (𝑥; 𝑎, 𝑏) = 𝑏−𝑎
1
, where 𝑎 and 𝑏 scaling.
are the lower and upper bounds, respectively. It provides In addition to varying job and machine counts, the in-
a straightforward way to explore a range of scenarios stances encompass different operational complexities and
without bias towards any particular value. These distri- constraints. For instance, some involve jobs with prece-
butions were selected due to their unique properties and dence constraints, necessitating certain jobs to be fin-
common use in modeling different real-world data types, ished before others begin. This complexity challenges al-
enhancing the diversity and comprehensiveness of the gorithms to find optimal solutions efficiently. The chosen
generated instances [15]. distributions—normal, exponential, and uniform—offer
Additionally, a random start is chosen for each job a spectrum of scenarios, ranging from predictable and
within a specified range for the release and due date in- evenly spread job times to highly variable and unpre-
tervals. The time interval between release and due dates dictable duration. This diversity ensures that the gener-
is determined based on the median processing time. A ated instances serve as robust benchmarks to evaluate
random value within the corresponding interval is gen- the performance of scheduling algorithms under varied
erated depending on the chosen distribution. This com- conditions.
prehensive approach ensures the creation of instances Moreover, a collection of 500 test instances has been
encompassing a wide range of scenarios, facilitating ro- generated and made publicly accessible through [16].
bust analyses and evaluations. These instances incorporate mixed distributions and
These steps culminate in constructing a JSP instance speed scalings, providing researchers with a compre-
(Line 8), incorporating the generated data. Finally, the hensive dataset to evaluate the efficacy of scheduling
algorithm returns the list 𝐺 containing the generated algorithms. The research group aims to foster collabora-
instances. This systematic approach ensures the creation tion and innovation in planning and scheduling research
of instances that cover diverse scenarios, which is crucialby facilitating access to these instances. Researchers can
for comprehensive analyses and evaluations. use these standardized problems to compare methods
and contribute to advancing scheduling solutions.
In summary, the generated instances cover a wide
3. Generated Problems range of job and machine configurations, distribution
types, and speed variations, making them suitable for
A comprehensive set of random instances has been gen- diverse scheduling and planning research applications.
erated following the procedure described in Algorithm Their availability for public use enhances their utility,
1. These instances exhibit diverse characteristics: the promoting collaboration and enabling continuous im-
number of jobs ranges from thirty to two hundred fifty, provement and benchmarking in the field.
and the number of machines ranges from three to twenty.
Normal, exponential, and uniform distributions were uti-
lized in the generation process. 4. Acknowledgments
Each instance was extended by relaxing release and
due date restrictions. Leveraging three different speed The authors gratefully acknowledge the financial sup-
scales, variations of each problem were created, maintain- port of the European Social Fund (Investing In Your Fu-
ture), the Spanish Ministry of Science (project PID2021- production scheduling model-the job shop schedul-
125919NB-I00), and valgrAI - Valencian Graduate School ing problem, Journal of Intelligent & Fuzzy Systems
and Research Network of Artificial Intelligence and the 45 (2023) 6959–6981. doi:10.3233/JIFS-222362.
Generalitat Valenciana, and co-funded by the European [10] A. Ham, M.-J. Park, K. M. Kim, Energy-aware flex-
Union. ible job shop scheduling using mixed integer pro-
gramming and constraint programming, Mathe-
matical Problems in Engineering 2021 (2021) 1–12.
References doi:10.1155/2021/8035806.
[11] J. Kotary, F. Fioretto, P. V. Hentenryck, Fast approxi-
[1] H. Xiong, S. Shi, D. Ren, J. Hu, A survey of
mations for job shop scheduling: A lagrangian dual
job shop scheduling problem: The types and
deep learning method, AAAI 36 (2022) 7239–7246.
models, Computers & Operations Research 142
doi:10.1609/aaai.v36i7.20685.
(2022) 105731. doi:https://doi.org/10.1016/
[12] L. Toma, M. Zajac, U. Störl, Solving distributed
j.cor.2022.105731.
flexible job shop scheduling problems in the wool
[2] D. B. M. M. Fontes, S. M. Homayouni, J. F. Gonçalves,
textile industry with quantum annealing, 2024.
A hybrid particle swarm optimization and simu-
arXiv:2403.06699.
lated annealing algorithm for the job shop schedul-
[13] J. Hoorn, The current state of bounds on bench-
ing problem with transport resources, European
mark instances of the job-shop scheduling prob-
Journal of Operational Research 306 (2023) 1140–
lem, Journal of Scheduling 21 (2017) 127–128.
1157. doi:https://doi.org/10.1016/j.ejor.
doi:10.1007/s10951-017-0547-8.
2022.09.006.
[14] D. Morillo Torres, F. Barber Sanchís, M. A.
[3] D. M. Torres, F. Barber, M. A. Salido, Psplib-
Salido Gregorio, Psplib-energy: Una extension de
energy: a extension of psplib library to assess the
la libreria psplib para la evaluacion de la optimiza-
energy optimization in the rcpsp, Inteligencia Ar-
cion energetica en el rcpsp, Inteligencia Artificial.
tificial 17 (2014) 48–61. doi:10.4114/intartif.
Revista Iberoamericana de Inteligencia Artificial 17
vol17iss54pp48-61.
(2014) 35–48.
[4] M. M. S. El-Kholany, M. Gebser, K. Schekotihin,
[15] L. Gui, X. Li, Q. Zhang, L. Gao, Domain knowledge
Problem decomposition and multi-shot asp solving
used in meta-heuristic algorithms for the job-shop
for job-shop scheduling, 2022.
scheduling problem: Review and analysis, Tsinghua
[5] C. Perez, M. A. Salido, D. Gurrea, A metaheuristic
Science and Technology null (2024) null. doi:10.
search technique for solving the warehouse stock
26599/tst.2023.9010140.
management problem and the routing problem in
[16] Planning, S. R. Group, Energy Instances for Sus-
a real company, in: Artificial Intelligence XXXVII,
tainable Job Shop Scheduling, 2024. doi:10.5281/
Springer International Publishing, Cham, 2020, pp.
zenodo.11640130.
187–201.
[6] M. Dai, D. Tang, A. Giret, M. A. Salido, Multi-
objective optimization for energy-efficient flexible
job shop scheduling problem with transportation
constraints, Robotics and Computer-Integrated
Manufacturing 59 (2019) 143–157. doi:https://
doi.org/10.1016/j.rcim.2019.04.006.
[7] C. Pérez, L. Climent, G. Nicoló, A. Arbelaez, M. A.
Salido, A hybrid metaheuristic with learning for
a real supply chain scheduling problem, Engi-
neering Applications of Artificial Intelligence 126
(2023) 107188. doi:https://doi.org/10.1016/
j.engappai.2023.107188.
[8] M. A. Salido, J. Escamilla, A. Giret, F. Barber,
A genetic algorithm for energy-efficiency in job-
shop scheduling, Int J Adv Manuf Technol
85 (2016) 1303–1314. doi:https://doi.org/10.
1007/s00170-015-7987-0.
[9] K. Jyothi, R. B. Dubey, Minimizing non-
processing energy consumption/total weighted tar-
diness & earliness, and makespan into typical