# A Robust Heuristics for the Online Job Shop Scheduling Problem
## 2 Motivation  
The job shop scheduling problem (JSSP) is a well-known intractable combinatorial optimization problem [3] that has been studied extensively since the 1950s [4; 5]. Besides the original application, the problem naturally appears in some other contexts, including the scheduling and rescheduling problem in the train traffic [6; 7]. Various scheduling strategies and intelligent algorithms have been proposed to solve the job shop scheduling problem. JSSP deals with scheduling a set of jobs on a set of machines under natural constraints, e.g., given order of operations of jobs on machines. The popular performance measures of JSSP are makespan, throughput time, earliness, tardiness, and due-date cost, among others. Makespan, the time at which processing of all jobs are completed, is the most commonly used performance measure for JSSP. Although a considerable amount of research has been dedicated to the development of efficient solving methods for JSSP, many of them were found to be unable to solve even relatively small-sized JSSP, e.g., an instance of size 10 \(\times\) 10 that was proposed before 1963 [8] has not been solved to optimality for more than a quarter of a century [9]. Even now, several benchmark instances of moderate size do not have known optimal solutions. Industry 4.0, with smart and distributed manufacturing systems, brings new challenges for extensive research [10]. It is well known that even the most simply stated optimization problems are known to be NP-hard, which, roughly speaking, means that there is no practical, i.e., quick and exact, optimization algorithm, assuming that the famous \(\mathrm{P}\
eq\mathrm{NP}\) conjecture is correct. The conjecture is among the most challenging theoretical problems and was included into the list of seven millennium problems [11]. Knowing that the problem of interest is computationally intractable implies that we may and should use heuristic approaches and that we also should aim to find nearly optimal solutions for which sometimes even approximation guaranties cannot be given. It is believed [12] that the best results are obtained when a special heuristics is designed and tuned for each particular problem. This means that the heuristics should be based on considerations of the particular problem and perhaps also on the properties of the most likely instances. On the other hand, it is useful to work within a framework of (one or more) metaheuristics which can be seen as general strategies to attack an optimization problem. Several examples are given, for example, in [13]. Hundreds of research papers and many textbooks were published on general and even on particular heuristics. For an extensive discussion of the meaning of terms heuristics and heuristic algorithms, see [14]. For a history of metaheuristics, we refer to [15]. In short, heuristics refer to problem-solving methods that are not guaranteed to find the optimal solution, but are instead intended to find a solution that is good enough in a reasonable amount of time. Heuristics are designed and tuned for each particular problem, and are based on considerations of the problem and the properties of the most likely instances. Metaheuristics refer to general strategies for attacking optimization problems using heuristics. For modeling practical problems in production, a number of variants of JSSP have been defined and studied [16]. Due to hardness of the basic problem and its variants, the exact algorithms, mostly based on the branch and bound method, can solve to optimality only in instances of very limited size. Therefore, many popular heuristics and metaheuristics were applied, and some more were designed to find near-optimal solutions of JSSP problem or its variants. We provide a sample of recent references in later sections. The simulation-based approach is widely adopted in industry as dispatching rules are readily implemented, are computationally efficient, and are robust to variability and uncertainty of a job shop [17].