The Job Shop Scheduling Problem (JSP) is a pivotal challenge in operations research and is essential for evaluating the efectiveness 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, reeflcting real-world scenarios and operational constraints. These instances facilitate comprehensive benchmarking and evaluation of scheduling algorithms, particularly in contexts of energy eficiency. 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-eficient scheduling solutions by providing diverse scenarios.
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 charnerstone in the realm of operations research and opti- acteristics significantly shapes benchmarking eforts in mization, representing a fundamental challenge pivotal JSP. Factors such as the number of jobs and machines, for evaluating algorithmic efectiveness 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 allocating 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 delprocess of benchmarking in JSP is multi-dimensional, ne- icate balance between energy consumption and schedulcessitating the definition and evaluation of metrics such ing decisions emerges as paramount in achieving energy as makespan, energy consumption, and tardiness to as- eficiency goals without compromising production tarsess scheduling eficiency and resource utilization [ 2]. gets [6].
Reference libraries and datasets like JSPLIB play an in- In recent years, the spotlight on addressing energy efdispensable 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 *20C2o4r,rGesirpoonnad,iSnpgaainuthor. 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(C. 0M00a0r-c0h0)0;20-090102-10-070923-948(3C5.-P40é5re7z()M;0.0S0a9l-i0d0o0)9-7525-9133 tations of these energy-eficient 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). and positive environmental impacts [10].
In conclusion, the imperative of energy eficiency in JSP research has become increasingly pronounced, paralleling the traditional focus on performance metrics [11].
Benchmarking is a linchpin in evaluating the eficacy of energy-eficient scheduling strategies, furnishing invaluable insights into their ramifications on production eficiency and energy consumption [ 12]. Manufacturers can embark toward more sustainable and economically viable operations by harnessing advanced optimization techniques and leveraging real-world implementations.
Test sets play a vital role in JSP research by providing a standardized platform for comparing algorithmic approaches. Their diversity enables researchers to evaluate various algorithms, from heuristics to exact methods, identifying strengths, weaknesses, and potential limitations across diferent contexts [ 13]. However, as industrial systems evolve, the complexity of real-world problems increases, necessitating the development or expansion of test sets to simulate real-world scenarios better.
To address this need, the proposed instance configurator operates with the following parameters: • = {0, . . . , }: the set of jobs. • = {0, . . . , }: the set of machines. • = {0, . . . , }: the set of speeds, indexed by in . • : the set of tasks in job , indexed by ∈ , ∀ ∈
, ∀ ∈ . • : the due date of task job ∀ ∈ , ∀ ∈ . • : the release date of task job ∀ ∈ , ∀ ∈ . • : the processing time of task job , ∀ ∈ , ∀ ∈
, ∀ ∈ . • : the energy consumption for processing task job , ∀ ∈ , ∀ ∈ , ∀ ∈ .
The process of configuring instances, managed by Algorithm 1, is initiated by receiving several input parameters: the number of instances to generate , the number of machines , the count of jobs , the number of tasks , the types of release and due dates , random seeds , and the distribution .
Subsequently, the algorithm executes a series of steps to generate instances systematically. The random seed is initialized to ensure reproducibility, and an empty list is created to store the generated instances (Line 2). The Algorithm 1 Instance Configurator input: Quantity of instances , Number of machines , Number of jobs , Number of tasks , Release and due date type , Random seed , Distribution output: Generated instances 1: () 2: ← [ ] 3: for from 1 to do 4: ← ( , , ) 5: ← (, , ) 6: ← (, , ) 7: , ← (, , ) 8: ← ∪ (, , , , ) 9: end for 10: return (1) (2) algorithm generates jobs and tasks within a loop iterating through each instance from 0 to − 1 (Line 4).
Next, each job operation’s processing times and energy consumption are generated.
() = ⌊− 100 × 100⌋ () = 4.0704 ×
log(2) log(1 + ( × 2.5093)3)
The functions responsible for generating the processing times (line 5) and energy consumption (line 6) for the combination of jobs, machines, and speeds are managed by functions () 1 and () 2, as illustrated in Figure 1 as studied in [14]. These functions balance the variables to establish a correlation between processing time and energy consumption. In these equations, represents the processing time for Equation () 1 and the energy consumption for Equation () 2. Speeds are generated by obtaining the energy consumption percentage for each speed using Equation () 1, which models an inverse relationship between processing time and energy consumption. This involves dividing the interval [0.5, 3] into || − 1 equal parts, where the boundaries of these new intervals correspond to the energy consumption percentages for each speed. Subsequently, Equation () 2 is utilized to determine the fraction of time corresponding to each speed.
Release and due dates are computed using functions based on the chosen distribution (Line 7). Each distribution ofers distinct characteristics suited for modeling various real-world scenarios.
The exponential distribution, defined by its probability density function (; ) = − , is ideal for modeling the time until an event occurs, such as machine failures or job arrivals, assuming a constant hazard rate > 0. Its mean is 1 . The Gaussian distribution, with mean and standard deviation , has a probability density function
− (− )2 (; , ) = √12 2 2 . This distribution repre- ing identical data but with diferent 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 fifthevenly 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 ina straightforward way to explore a range of scenarios stances encompass diferent operational complexities and without bias towards any particular value. These distri- constraints. For instance, some involve jobs with precebutions were selected due to their unique properties and dence constraints, necessitating certain jobs to be fincommon use in modeling diferent real-world data types, ished before others begin. This complexity challenges alenhancing the diversity and comprehensiveness of the gorithms to find optimal solutions eficiently. The chosen generated instances [15]. distributions—normal, exponential, and uniform—ofer
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 unpretervals. The time interval between release and due dates dictable duration. This diversity ensures that the generis 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 eficacy of scheduling algorithm returns the list containing the generated algorithms. The research group aims to foster collaborainstances. This systematic approach ensures the creation tion and innovation in planning and scheduling research of instances that cover diverse scenarios, which is crucial by 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 imnumber 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 utilized in the generation process. 4. Acknowledgments
Each instance was extended by relaxing release and due date restrictions. Leveraging three diferent speed The authors gratefully acknowledge the financial supscales, variations of each problem were created, maintain- port of the European Social Fund (Investing In Your Fu