《2016 A Disjunctive Graph for the Job Shop with Several Robots》.pdf

Regular Papers A Disjunctive Graph for the Job-Shop with Several Robots Philippe Lacomme, Mohand Larabi Université Blaise Pascal, LIMOS (UMR CNRS 6158), 63177 Aubière Cedex, France, {placomme, larabi }@isima.fr Nikolay Tchernev IUP « Management et gestion des entreprises », Université d’Auvergne, LIMOS (UMR CNRS 6158), 26, av. Léon Blum, Clermont Ferrand, France (tchernev@isima.fr) This paper addresses the scheduling problem in a job-shop where the jobs have to be transported between the machines by several transport robots. The problem can be efficiently modeled by a disjunctive graph and any solution can be fully defined by an orientation of the graph. The objective is to determine a schedule of machine and transport operations as well as an assignment of robots to transport operations with minimal makespan. We present: (i) a problem representation using an appropriate disjunctive graph; (ii) a solution representation based on 3 vectors consisting of machine disjunctions, transport disjunctions and robots assignments; (iii) a new problem-specific properties to define local search algorithms. Computational results are presented for test data arising from Bilge and Uluzoy’s benchmark instances enlarged by transportation, empty moving times for each robot. This paper is a step forward definition of an efficient approach arising a job-shop with