A parallel heuristic for hybrid job shop scheduling problem considering conflict-free AGV routing

In this study, a novel and computationally efficacious Parallel Two-Step Decomposition-Based Heuristic (PTSDBH) and a Mixed Integer Linear Programming (MILP) are developed to tackle the concurrent scheduling of jobs and Automated Guided Vehicles (AGVs) or transporters in a hybrid job shop system. Finite multiple AGVs, AGV eligibility, job's alternative process routes, job re-entry, and conflict-free AGV routing are considered. As far as the authors know, the importance of conflict-free routing for AGVs has not been featured in any of the past studies. Conflict-free AGV routing is an indispensable technicality, specifically where AGVs are the main mean of transportation as AGVs may collide on routes and the whole system ends up in breakdown. To avoid this issue, a conflict-free routing strategy is considered. Utilizing the parallel computing approach, PTSDBH is capable of tackling large-sized problems in remarkably shorter runtimes. To support this, PTSDBH is compared against three literarily well-known metaheuristics; i.e., Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) along with TSDBH (i.e., the single-core variant of PTSDBH) on three different-sized sets of benchmark instances. The results reveal that PTSDBH and TSDBH produce the same objective values and outperform the metaheuristics in terms of the quality of objective value. However, the runtimes of TSDBH are considerably higher than those of PTSDBH as it only uses one core to process. Finally, employing Nemenyi's post-hoc procedure for Friedman's test and the convergence plot, it is supported that the objective values generated by PTSDBH and TSDBH are significantly more desirable than those generated by the metaheuristics.