In modern manufacturing, scheduling plays a critical role in optimizing production efficiency, particularly in flexible job shop environments where multiple machines can process various operations of workpieces like gear shafts. The gear shaft, as a key component in mechanical systems, requires precise and efficient scheduling to minimize completion times and enhance overall productivity. This paper addresses the flexible job shop scheduling problem (FJSP) for gear shaft production by proposing an improved hybrid genetic algorithm (IGASA) that integrates simulated annealing (SA) to overcome limitations of traditional genetic algorithms (GA). We focus on minimizing the maximum completion time (makespan) while considering constraints such as machine flexibility and operation sequences. The algorithm incorporates a global-local-random (GLR) population initialization strategy, specialized crossover and mutation operations, and SA with neighborhood structures to improve solution quality and convergence speed. Through extensive simulations using standard benchmarks and real-world gear shaft data, we demonstrate the effectiveness of our approach in reducing makespan and enhancing scheduling performance.
The FJSP is an extension of the classic job shop scheduling problem, where each operation of a workpiece, such as a gear shaft, can be processed on any machine from a set of available machines. This flexibility introduces complexity, making FJSP an NP-hard problem. For gear shaft manufacturing, which involves multiple operations like turning, drilling, and milling, efficient scheduling is crucial to avoid bottlenecks and reduce idle time. The mathematical model for FJSP involves parameters such as the number of workpieces (n), machines (m), and operations per workpiece. Let J = {J1, J2, …, Jn} represent the set of workpieces, where each Ji corresponds to a gear shaft. M = {M1, M2, …, Mm} denotes the set of machines, and O = {Oi,j} represents the operations, with Oi,j being the j-th operation of workpiece i. The processing time Ti,h,k is the time required for operation h of workpiece i on machine k. The start and completion times for operation h of workpiece i are Ts,i,h and Tc,i,h, respectively, and the makespan Cmax is the maximum completion time across all workpieces. The objective is to minimize Cmax, subject to constraints such as operation precedence, machine availability, and non-negative times. The constraints can be formulated as follows:
$$ T_{s,i,h} + x_{i,j,k} \times T_{i,h,k} \leq T_{c,i,h} \quad \text{for } i=1,2,\dots,n; j=1,2,\dots,m; h=1,2,\dots,h_i $$
$$ T_{c,i,h} \leq T_{s,i,(h+1)} \quad \text{for } i=1,2,\dots,n; h=1,2,\dots,h_i-1 $$
$$ T_{c,i,h_i} \leq C_{\text{max}} \quad \text{for } i=1,2,\dots,n $$
$$ \sum_{k=1}^{m_{i,h}} x_{i,j,k} = 1 \quad \text{for } h=1,2,\dots,h_i; i=1,2,\dots,n $$
$$ \sum_{i=1}^{n} \sum_{h=1}^{h_i} y_{i,j,k} = x_{i,k,j} \quad \text{for } i=1,2,\dots,n; k=1,2,\dots,m $$
$$ T_{s,i,h} \geq 0; \quad T_{c,i,h} \geq 0 \quad \text{for } i=1,2,\dots,n; h=1,2,\dots,h_i $$
Here, xi,j,k is a binary decision variable indicating whether operation Oi,j is assigned to machine k, and yi,j,k indicates the sequence of operations on machines. The fitness function for optimization is defined as the inverse of the makespan: fg = 1 / Cmax. This model forms the basis for our algorithm development, aiming to efficiently schedule gear shaft production in flexible workshops.
Our improved hybrid genetic algorithm (IGASA) builds upon the traditional GA by incorporating enhancements in population initialization, crossover, mutation, and local search via simulated annealing. The algorithm begins with a multi-layer chromosome encoding scheme, consisting of an operation layer, a machine layer, and a time layer. For example, a chromosome segment (1,4,2)^T indicates that the first operation of workpiece 1 (e.g., a gear shaft) is processed on machine 4 with a time of 2 units. This encoding allows for efficient representation of schedules. The population initialization employs a GLR strategy to generate diverse and high-quality initial solutions. In the global selection phase, we accumulate processing times in an array and select machines with the smallest cumulative times to balance loads. Local selection resets the array for each workpiece to increase diversity, while random selection assigns machines arbitrarily from the available set. This approach ensures a robust starting population for the evolutionary process.
The selection operation uses a tournament method to choose individuals with higher fitness values for reproduction, promoting the survival of better solutions. Crossover operations are applied separately to the operation and machine layers. For the operation layer, we use an improved position-based crossover (IPOX), which preserves the sequence of operations from parents while maintaining machine assignments. For instance, given two parent chromosomes, we randomly partition the workpieces into groups and copy operations from one parent to the offspring based on group membership, ensuring feasibility. For the machine layer, uniform crossover (UX) is employed, where a binary mask determines which genes are swapped between parents, introducing variability in machine assignments. This is particularly important for gear shaft scheduling, as it allows exploration of different machine combinations for operations like grinding or drilling. Mutation operations involve an insertion-based strategy that selects a highly loaded machine and reassigns one of its operations to a less loaded machine, thereby balancing the workload and improving solution quality. The steps include identifying the machine with the highest load, selecting a random operation, and swapping it to another machine, which enhances diversity and prevents premature convergence.
To address the local optima issue in GA, we integrate simulated annealing (SA) with three neighborhood structures: N1, N2, and N3. N1 swaps two randomly selected operations in the sequence; N2 inserts an operation before another in the sequence; and N3 reassigns a randomly chosen operation to a different machine. The SA process starts with an initial temperature T = 100 and a cooling rate K = 0.9. According to the Metropolis criterion, a new solution is accepted if it improves the objective function; otherwise, it is accepted with a probability exp(-ΔE / βT), where ΔE is the change in energy (objective value) and β is the Boltzmann constant. This hybrid approach allows the algorithm to escape local optima and explore a broader solution space. The overall IGASA procedure involves initializing parameters, encoding chromosomes, generating the initial population with GLR, evaluating fitness, performing selection, crossover, and mutation, and then applying SA to refine solutions. The algorithm iterates until a maximum number of generations is reached, outputting the best schedule for gear shaft production.
We conducted experiments to validate the performance of IGASA using standard benchmarks and a real-world case study involving gear shaft manufacturing. The experimental setup included a Windows 11 system with 16 GB RAM and an i7-13650HX processor, implemented in MATLAB. Parameters were set as follows: population size = 150, crossover probability Pc = 0.9, mutation probability Pm = 0.1, and maximum iterations = 100. For SA, initial temperature T = 100 and decay factor K = 0.9. We first tested IGASA on five benchmark instances (Kacem01 to Kacem05) and compared it with traditional GA and other recent algorithms. The results, averaged over 20 runs, are summarized in Table 1, showing that IGASA achieves lower makespan values, demonstrating its superiority in solving FJSP for various configurations.
| Instance | GA | Reference [16] | Reference [17] | IGASA Best | IGASA Average |
|---|---|---|---|---|---|
| Kacem01 | 12.00 | 11.00 | 11.00 | 11.00 | 11.05 |
| Kacem02 | 16.00 | 15.00 | 14.00 | 14.00 | 14.65 |
| Kacem03 | 13.00 | 12.00 | 11.00 | 11.00 | 11.00 |
| Kacem04 | 7.00 | 7.00 | 7.00 | 7.00 | 7.45 |
| Kacem05 | 23.00 | 11.00 | 11.00 | 11.00 | 11.90 |
For the gear shaft case study, we considered a workshop with 15 machines (e.g., lathes, drills, mills) processing 10 workpieces, each requiring 5 to 8 operations. The machine options and processing times for each operation are detailed in Table 2 and Table 3. For instance, the first operation of workpiece J1 (a gear shaft) can be processed on machines 1, 2, or 3 with times 13, 18, or 14 seconds, respectively. This flexibility is common in gear shaft production, where operations like turning or finishing may vary based on machine capabilities. We ran IGASA, GA, and a basic hybrid GA-SA (GASA) for 10 independent runs, each with 100 iterations. The average and minimum makespan values over iterations are plotted in Figures 1 and 2, showing that IGASA converges faster and achieves lower makespan values. Specifically, the minimum makespan for IGASA was 478 seconds, compared to 522 seconds for GA and 508 seconds for GASA, representing an 8.43% improvement in production efficiency for gear shaft scheduling.
| Operation | J1 | J2 | J3 | J4 | J5 | J6 | J7 | J8 | J9 | J10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 |
| 2 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 1,2,3 | 8 | 8 | 1,2,3 |
| 3 | 4,5 | 4,5 | 4,5 | 4,5 | 4,5 | 4,5 | 4,5 | 1,2,3 | 1,2,3 | 6,7 |
| 4 | 6,7 | 6,7 | 6,7 | 11 | 11 | 11 | 12,13,14,15 | 10 | 10 | – |
| 5 | 8 | 8 | 8 | 6,7 | 6,7 | 6,7 | 11 | 12,13,14,15 | 12,13,14,15 | – |
| 6 | 9,10 | 9,10 | 9,10 | 8 | 8 | 12,13,14,15 | 6,7 | 6,7 | – | – |
| 7 | 9,10 | 9,10 | – | – | – | – | – | – | – | – |
| 8 | 8 | – | – | – | – | – | – | – | – | – |
| Operation | J1 | J2 | J3 | J4 | J5 | J6 | J7 | J8 | J9 | J10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 13,18,14 | 16,15,17 | 22,27,25 | 24,28,21 | 40,44,42 | 41,48,44 | 18,22,17 | 39,46,41 | 43,46,42 | 26,29,31 |
| 2 | 12,9,11 | 14,18,16 | 28,31,34 | 26,31,22 | 47,46,47 | 36,42,36 | 21,26,22 | 22 | 31 | 32,37,33 |
| 3 | 31,36 | 33,37 | 46,40 | 42,49 | 58,64 | 20,25 | 67,74 | 29,33,27 | 35,37,31 | 82,96 |
| 4 | 67,62 | 52,56 | 67,75 | 30 | 39 | 21 | 63,66,84,81 | 10 | 10 | – |
| 5 | 7 | 9 | 8 | 54,58 | 98,108 | 98,104 | 15 | 113,115,81,86 | 124,121,79,93 | – |
| 6 | 28,24 | 32,31 | 41,49 | 6 | 6 | 72,74,91,96 | 91,127 | 98,132 | – | – |
| 7 | 47,42 | 178,195 | – | – | – | – | – | – | – | – |
| 8 | 11 | – | – | – | – | – | – | – | – | – |
The convergence curves for average and minimum makespan clearly indicate that IGASA outperforms other algorithms. For example, the average makespan decreases rapidly with IGASA, reaching stable values earlier than GA and GASA. This is attributed to the GLR initialization and SA enhancements, which provide a better exploration-exploitation balance. The Gantt chart for the gear shaft schedule generated by IGASA (Figure 3) illustrates an optimized timeline where operations are efficiently assigned to machines, minimizing idle times and overlaps. In conclusion, our improved hybrid genetic algorithm effectively addresses the FJSP for gear shaft production by integrating advanced strategies that enhance solution quality and convergence. Future work will extend this approach to multi-objective optimization, considering factors like energy consumption and machine utilization, to further improve gear shaft manufacturing processes.
In summary, the gear shaft flexible workshop scheduling problem is a complex challenge that requires sophisticated algorithms for optimal performance. Our IGASA algorithm, with its GLR initialization, IPOX and UX crossover, insertion mutation, and SA-based local search, demonstrates significant improvements in reducing makespan. The experimental results on both benchmarks and real-world gear shaft data confirm its efficacy, making it a valuable tool for modern manufacturing systems. By continuously refining such algorithms, we can achieve higher efficiency and productivity in gear shaft production and beyond.