# A Robust Heuristics for the Online Job Shop Scheduling Problem
## 4 Our Approach
### Introducing the Parameter Temperature  
To achieve this, we have borrowed the idea of temperature used in the popular heuristics simulated annealing that is inspired by analogy with statistical mechanics [34]. Simulated annealing involves gradually decreasing the temperature of a system to allow it to settle into a lower energy state. In our context, we introduced the temperature parameter to add some control of the importance of weights in the randomized choice of the next job to be chosen.  
In our method, we have implemented analogous idea to increase the randomness of the solution search. This is achieved through the use of a temperature parameter, denoted as \(T\). Unlike traditional simulated annealing algorithms, where the temperature decreases over time, we set \(T\) to a constant value that ranges among runs of simulations. The idea of fixed temperature schedule is well known [57; 58]. The purpose of this approach is to maintain a certain level of randomness throughout the entire search process, which can lead to the discovery of better solutions that may be missed if the randomness is decreased too quickly.  
In the Formula (4) below, \(T\) is the temperature parameter, and \(r_{i}\) is a random value drawn from a uniform distribution between 0 and 1. Parameter \(T\) can be seen as a change of base of the exponential expression as \(e^{\frac{w_{i}}{T}}=(e^{\frac{1}{T}})^{w_{i}}={b_{T}}^{w_{i}}\). Clearly, large \(T\) makes base \(B_{T}\) close to \(e^{0}=1\), implying that the weights \(w_{i}\) tend to be ignored. The priority rule, thus, gets very similar to the uniform random choice. On the other hand, very small \(T\) means that a larger weight \(w_{i}\) very likely means the operation of the job will be selected. The factor \(r_{i}\) adds some random noise to the weight calculation, which decreases as the temperature parameter decreases.  
Specifically, we modified the weight calculation Formula (3) to include the temperature parameter, as follows:  
Figure 1: Illustration of the probabilistic job selection process. Due to the stochastic nature of the algorithm, job C1 interrupts the expected sequence and is processed earlier than anticipated.  
\[\Omega_{ji}=r_{i}\cdot e^{\omega_{ji}(t)/T}=r_{i}\cdot(e^{\frac{1}{T}})^{\omega_{ji} (t)}=r_{i}\cdot(e^{\frac{1}{T}})^{\omega_{ji}(t)}=r_{i}\cdot b_{T}{}^{\omega_{ji} (t)}\,. \tag{4}\]  
By introducing this level of randomness, we were able to explore the search space more effectively, and found that our algorithm produced even better results than before. We have validated the effectiveness of our modified algorithm by comparing its performance to existing methods and found that it it is competitive both in terms of solution quality and computation time. By combining the strengths of both the weighting system and simulated annealing, we have achieved significant improvements in the flow time of operations across all machines. Overall, from experimental results we observe that our heuristic method represents a powerful and flexible approach for solving complex job shop scheduling problems. Through the incorporation of innovative techniques such as simulated annealing, we have been able to achieve highly competitive results and make significant contributions to the field of production planning and scheduling.