# A Robust Heuristics for the Online Job Shop Scheduling Problem
## 4 Our Approach
### Priority Queues at Machines  
Our approach is based on the idea of using buffer states (\(B_{i}\)) for each machine (\(M_{i}\)) to hold the remaining operations while the machine is processing one operation. The buffer states allow for the prioritization of operations based on their weight (\(\omega_{ji}\)) and arrival time in the buffer. In our method, each operation \(O_{ji}\) of job \(J_{j}\) that comes to a specific machine \(M_{i}\) first goes through the buffer state, i.e., enters the priority queue \(B_{i}\). In the case where the buffer \(B_{i}\) at machine \(M_{i}\) has multiple orders (operations to be performed) or the machine \(M_{i}\) is occupied or nonoperational, the orders have to wait in the queue \(B_{i}\) for a change in the state of the machine \(M_{i}\). The queue is a priority queue in the sense that operations in the buffer can overtake each other based on the weight of each operation (\(\omega_{ji}\)) and the arrival time of each operation in the buffer. The lower the weight, the higher priority it has. The choice of the weights assigned to each job in the buffer state is crucial for the performance of the system. Traditionally, this weight has been assigned using a uniform random function. However, recent research has shown [56] that incorporating the remaining processing time of each operation on all machines and the sum of remaining processing times of all operations on all machines can lead to better results. To this end, a new formula has been proposed for calculating the weight of each operation. The formula takes into account the remaining processing time of the jobs that have operations who are waiting to be processed by machine \(M_{i}\) at time \(t\). The formula takes into account the remaining processing time of the job \(J_{j}\) associated with the operation at time \(t\) it is waiting to be processed by machine \(M_{i}\), denoted by \(p_{ij}(t)\). Note that these values are known in advance as they only depend on the time needed to perform the operations of job \(J_{j}\), hence \(p_{ij}(t)=p_{ij}\). Formally, the weight of job \(J_{j}\) at machine \(M_{i}\) is defined as follows. Assume that operation \(O_{ji}\) of job \(J_{j}\) at machine \(M_{i}\) is at \(k\)-th position of job \(J_{j}\), so its remaining processing time is:  
\[p_{ji}=\Sigma_{\ell=k}^{n}\tau_{j\ell}. \tag{1}\]At the time the new job is chosen from the queue \(B_{i}\), the weight of operation \(O_{ji}\) (job \(J_{j}\)) is:  
\[\omega_{ji}(t)=\frac{p_{ji}}{\Sigma_{I_{\ell}\in B_{i}}p_{tj}(t)} \tag{2}\]  
where the sum in denominator runs over all operations in the queue \(B_{i}\) at time \(t\). The weight is, thus, changing in time, depending on the current status of the jobs. The weights are used to define the probability of choosing the next job to be processed. More precisely, let \(J_{j}\) be a job in the buffer at machine \(M_{i}\) at time \(t\). Then, the probability of choosing \(J_{j}\) is proportional to:  
\[\Omega_{ji}(t)=e^{\omega_{ji}(t)} \tag{3}\]  
Hence, the probability of choosing the job \(J_{j}\) in the queue of machine \(M_{i}\) at time \(t\) is \(P_{j}=\frac{1}{5}e^{\omega_{ji}(t)}\), where \(S=\sum\Omega_{ji}(t)\), the sum running over all jobs in the queue of machine \(M_{i}\) at time \(t\). In the case of the rare event where there are two or more operations in the buffer state \(B_{i}\) at the same time and they have the same weight, the FIFO (First In First Out) rule is applied, which means that priority is given to the operation that arrived earlier. Coded in a pseudo programming language, the choice of the next job is made as follows. ```
Data: Unfinished jobs, machines \(M_{i}\), buffers \(B_{i}\) for each machine, random seed \(s\) Result: Optimal or near-optimal schedule.