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