Simultaneous Scheduling of Machines and a Single Moving Robot in a Job Shop Environment by Metaheuristics based Clustered Holonic Multiagent Model

Abstract

In systems based robotic cells, the control of some elements such as transport robot has some difficulties when planning operations dynamically. The Job Shop scheduling Problem with Transportation times and a Single Robot (JSPT-SR) is a generalization of the classical Job Shop scheduling Problem (JSP) where a set of jobs additionally have to be transported between machines by a single transport robot. Hence, the JSPT-SR is more computationally difficult than the JSP presenting two NP-hard problems simultaneously: the job shop scheduling problem and the robot routing problem. This paper proposes a hybrid metaheuristic approach based on clustered holonic multiagent model for the JSPT-SR. Firstly, a scheduler agent applies a Neighborhood-based Genetic Algorithm (NGA) for a global exploration of the search space. Secondly, a set of cluster agents uses a tabu search technique to guide the research in promising regions. Computational results are presented using benchmark data instances from the literature of JSPT-SR. New upper bounds are found, showing the effectiveness of the presented approach.