An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs

This paper concerns with the Job Shop Scheduling Problem (JSSP) considering the transportation times of the jobs from one machine to another. The goal of a basic JSSP is to determine starting and ending times for each job in which the objective function can be optimized. In here, several Automated Guided Vehicles (AGVs) have been employed to transfer the jobs between machines and warehouse located at the production environment. Unlike the advantages of implemented automatic transportation system, if they are not controlled along the routes, it is possible that the production system encounters breakdown. Therefore, the Conflict-Free Routing Problem (CFRP) for AGVs is considered as well as the basic JSSP. Hence, we proposed a mathematical model which is composed of JSSP and CFRP, simultaneously and since the problem under study is NP-hard, a two stage Ant Colony Algorithm (ACA) is also proposed. The objective function is to minimize the total completion time (make-span). Eventually, in order to show the model and algorithm’s efficiency, the computational results of 13 test problems and sensitivity analysis are exhibited. The obtained results show that ACA is an efficient meta-heuristic for this problem, especially for the large-sized problems. In addition, the optimal number of both AGVs and rail-ways in the production environment is determined by economic analysis.