In this paper, a parallel multi-path variant of the well-known TSAB algorithm for the job shop scheduling problem is proposed. Coarse-grained parallelization method is employed, which allows for great scalability of the algorithm with accordance to Gustafon’s law. The resulting P-TSAB algorithm is tested using 162 well-known literature benchmarks. Results indicate that P-TSAB algorithm with a running time of one minute on a modern PC provides solutions comparable to the ones provided by the newest literature approaches to the job shop scheduling problem. Moreover, on average P-TSAB achieves two times smaller percentage relative deviation from the best known solutions than the standard variant of TSAB. The use of parallelization also relieves the user from having to fine-tune the algorithm. The P-TSAB algorithm can thus be used as module in real-life production planning systems or as a local search procedure in other algorithms. It can also provide the upper bound of minimal cycle time for certain problems of cyclic scheduling.
The article introduces an innovative approch for the inspection challenge that represents a generalization of the classical Traveling Salesman Problem. Its priciple idea is to visit continuous areas (circles) in a way, that minimizes travelled distance. In practice, the problem can be defined as an issue of scheduling unmanned aerial vehicle which has discrete-continuous nature. In order to solve this problem the use of local search algorithms is proposed.