Genetic algorithms using multi-objectives in a multi-agent system

摘要

We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram's optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current solution is a way of leading to a better allocation. The goal is to reduce the delay in an existing solution and to obtain better scheduling at the end of the planning. We propose an original solution based on genetic algorithms which allows to determine a set of good heuristics for a given benchmark. From these results, we propose a dynamic model based on the contract-net protocol. This model describes a way to obtain new schedulings with agent negotiations. We implement the agent paradigm on parallel machines. After a description of the problem and the genetic method we used, we present the benchmark calculations that have been performed on an SGI Origin 2000. The interpretation of these is a way to refine heuristics given by our evolution process and a way to constrain our agents based on the contract-net protocol. This dynamic model using agents is a way to simulate the behavior of entities that are going to collaborate to improve the Gantt diagram.