# Special Issue on Exact and Heuristic Scheduling Algorithms
## 2 Main Results of the Special Issue
Polynomial algorithms are given for three special cases, namely a two-machine job shop problem with two jobs and allowed recirculation, the two-machine flow shop problem and an \(m\)-machine flow shop problem with two jobs, each with the objective to minimize the makespan. Finally, some special cases with open complexity status are mentioned. The paper [7] analyzes the connections between usual scheduling criteria typically applied to flow shop problems like the makespan or idle time and customary shop floor performance measures such as work-in-progress or throughput. The authors setup a deep experimental analysis consisting in finding optimal or near-optimal schedules under several scheduling criteria and then investigating how these schedules behave in terms of different shop floor performance measures for several instances with different structures of the processing times. In particular, detailed computational results have been presented for instances with up to 200 jobs and 50 machines. It turned out that some of the scheduling criteria are poorly related to shop floor performance measures. In particular, the makespan performed only well with respect to throughput. On the other hand, the minimization of total completion time appeared to be better balanced in terms of shop floor performance. The paper finishes with suggesting some aspects for future work. The paper [8] addresses a two-machine job shop scheduling problem, where the job duration may take any real value from a given segment. A stability approach [9] is applied to this uncertain scheduling problem. The scheduling decisions in the stability approach may consist of two successive phases: the first off-line phase, which is finished before starting the realization of a schedule, and the second on-line phase of scheduling, which is started with the beginning of the schedule realization. Using the information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set (DS) of schedules based on sufficient conditions for schedule dominance. The DS optimally covers all possible scenarios of the job durations in the sense that for each possible scenario, there exists at least one schedule in the DS which is optimal. Based on the DS, a scheduler can choose a schedule, which is optimal for the majority of possible scenarios. Polynomial algorithms have been developed for testing a set of conditions for schedule dominance. The conducted computational experiments on the randomly generated instances have shown the effectiveness of the developed algorithms. Most instances from the nine tested classes were optimally solved. If the maximum error was not greater than 20%, then more than 80% of the tested instances were optimally solved. If the maximum error was equal to 50%, then 45% of the tested instances from the nine classes were optimally solved. The paper [10] deals with the Euclidean version of the traveling salesman problem (TSP), where the locations of the cities are points in the two-dimensional Euclidean space and the distances are Euclidean ones. For this problem, the authors suggest fast and easily implementable heuristics. They consist of three phases: construction, insertion and improvement. The first two phases run in \(O(n)\) time with \(n\) being the number of points, and the number of improvement repetitions in the third phase is bounded by a small constant. The practical behavior of the suggested heuristics has been tested on 218 benchmark instances from several well-known libraries for TSP instances. In particular, the authors grouped the instances into small ones (up to 199 points), medium-size ones (between 200 and 9999 points) and large instances (between 10,000 and 250,000 points), and results for two very large instances with 498,378 and 744,410 points were also given.