# A Robust Heuristics for the Online Job Shop Scheduling Problem
###### Abstract  
The job shop scheduling problem (JSSP) is a popular NP-hard problem in combinatorial optimization, due to its theoretical appeal and its importance in applications. In practical applications, the online version is much closer to the needs of smart manufacturing in Industry 4.0 and 5.0. Here, the online version of the job shop scheduling problem is solved by a heuristics that governs local queues at the machines. This enables a distributed implementation, i.e., a digital twin can be maintained by local processors which can result in high speed real time operation. The heuristics at the level of probabilistic rules for running the local queues is experimentally shown to provide the solutions of quality that is within acceptable approximation ratios to the best known solutions obtained by the best online algorithms. The probabilistic rule defines a model which is not unlike the spin glass models that are closely related to quantum computing. Major advances of the approach are the inherent parallelism and its robustness, promising natural and likely successful application to other variations of JSSP. Experimental results show that the heuristics, although designed for solving the online version, can provide near-optimal and often even optimal solutions for many benchmark instances of the offline version of JSSP. It is also demonstrated that the best solutions of the new heuristics clearly improve over the results obtained by heuristics based on standard dispatching rules. Of course, there is a trade-off between better computational time and the quality of the results in terms of makespan criteria. job shop scheduling problem; online algorithm; heuristics; simulation; digital twin; smart manufacturing [1]  
can naturally be implemented in the environment with changing features, e.g., changes of orders, failure of machine(s), etc. Similar approach may be used also in the case when the problem is offline in the sense that we have a complete list of the jobs known, but have a very short time to find a solution as the production must start promptly. In other words, there is no profit if the optimal makespan solution is found after the production process is already finished. On the other hand, we emphasize that we focus on the basic JSSP here because we want to evaluate the performance of the basic heuristics on the popular datasets. The performance, however, has to be judged keeping in mind that online algorithms clearly have a handicap when compared with the offline algorithms. The main contributions of the work reported here are the following:  
1. We design a model for randomized heuristics based on priority rules that can approximately solve online problems;
2. We provide a definition of a novel type of priority rule based on the remaining processing time of jobs, using a combination of two parameters;
3. We give experimental evidence that the approach can provide, although it is an online algorithm, optimal or near-optimal solutions on a set of benchmark problems for the offline JSSP. Furthermore, we provide evidence that the approach is robust with regard to both parameters in the sense that near-optimal solutions are reported for values of parameters within reasonably large intervals. We wish to note that the approach using the priority rules at the machines is not new; however, to the best of our knowledge, the applications are limited to the standard dispatching rules like first-in-first-out (FIFO), shortest processing time (SPT), and longest processing time (LPT) that are easy to use but are not accurate enough for solving tough scheduling problems [2]. Randomization, which we introduce, is a novel idea that combines the positive features of the standard rules with the diversity that comes from random decisions based on Boltzmann distribution. A comparison is provided showing that restarted simulations using the here-proposed randomized dispatching rules clearly outperform the standard deterministic dispatching rules.