# A Robust Heuristics for the Online Job Shop Scheduling Problem
## 3 Preliminaries
### Variations of the JSSP  
The job shop scheduling problem is among the most popular optimization problems due to its importance in practical situations. After the first paper on the job shop scheduling problem [19], a countless number of studies have been published. See, e.g., a survey on deterministic job shop scheduling [20] and another survey on fuzzy versions of the problem [21]. The survey paper [22] in a recent special issue [23] dealt with the design, balancing, and scheduling of assembly and production lines under inaccurate data. Various applications led to generalizations and variations of the original problem [24]. The importance of the problem and its known complexity motivated the application of many heuristics and metaheuristics. In [16], a general framework for automatic design for shop scheduling strategies based on hyper-heuristics has been constructed, and various state-of-the-art technical points in the development process are summarized. Some existing types of shop scheduling strategies were summarized and classified using a new classification method.  
In particular, the smart manufacturing and Industry 4.0 reinforced the needs for solving real time scheduling problems. The authors of the review [16] proposed a classification of JSSP. For example, DFJSPP stands for dynamic flexible job shop scheduling problem. This variation is an example which nicely illustrates some of the many challenges that the practical scheduling adds to the basic problem. Two further examples include minimum-energy scheduling [25] and bi-objective dynamic open shop scheduling [26]. Due to the high complexity of practical problems, the actual shop production environment may change at any time (e.g., order cancellation, addition, advance of delivery) [27]; thus, for each disturbance, the solver that is not adapted to the flexible JSSP may spend much time for rescheduling.  
The digital twin is one of the main concepts associated with the Industry 4.0 wave [28]. It provides virtual representations of systems along their life cycle. Optimization and decision making would then rely on the data that are updated in real time with the physical system, through synchronization enabled by sensors. Corresponding optimization tools, therefore, cannot rely on full information given a priori. Hence, in most cases, the online versions of the optimization problems have to be solved in this context. As explained later, our approach is based on a heuristics that governs local queues at the machines. In principle, 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. Furthermore, the approach is robust in the sense that various changes can be handled without severe consequences.  
However, in order to evaluate the approach, we have used some popular benchmark instances for the offline version of the problem. The reason for this is that there are no standard benchmark instances for the online version, while the offline datasets are well known [29] and can be used for both versions. We wish to emphasize that the online versions of the problems are usually more complex than the offline versions of the problem. Usually, competitive analysis [30] is used to obtain competitive ratios between the versions. For example, [PERSON] and [PERSON] [31] show that 2 is a tight lower bound on the competitive ratio for a problem with two machines and the objective of minimizing the makespan.