Multi-agent system for distributed manufacturing scheduling with Genetic Algorithms and Tabu Search

A computerized scheduling method stored in a memory and executed on one or more processors, the method comprising:

• receiving for each of a plurality of jobs;
• receiving release dates for each job;
• grouping the plurality of operation due dates and the plurality of operation release dates into constituent single machine scheduling problems;
• for each single machine scheduling problem, determining estimated job release dates and estimated job due dates based on the received operation estimated due dates and operation estimated release dates;
• allocating each single machine scheduling problem to each of a plurality of resource agents in a multi-agent system;
• solving each allocated single machine scheduling problem using a genetic algorithm thereby obtaining corresponding near optimal single machine scheduling problem solutions;
• integrating the obtained near optimal single machine scheduling problem solutions into a main job shop scheduling problem solution;
• verifying a feasibility of the main scheduling problem solution, said resource agents being capable of later cooperation to overcome inter-agent constraints of the main scheduling problem solution;
• and
• outputting the main job shop scheduling problem solution.

A computerized scheduling system, comprising:

• a hybrid scheduling module in a multi-agent system, the hybrid scheduling module including logic configured to:
• decompose a main job shop scheduling problem into a plurality of single machine scheduling problems;
• allocate each single machine scheduling problem to a plurality of resource agents in a multi-agent system, each resource agent:
• solving each constituent single machine scheduling problem using a genetic algorithm thereby obtaining corresponding near optimal single machine scheduling problem solutions;
• integrate the plurality of near optimal single machine scheduling problem solutions into a main job shop scheduling problem solution;
• and
• output the main job shop scheduling problem solution.

A computerized scheduling system, the system comprising:

• a user interface to receive due dates for each of a plurality of jobs, to receive a plurality of release times for each of the number of jobs, and to receive a structure for each of the lobs;
• a hybrid scheduling module;
• the hybrid scheduling module including logic configured to:
• group the plurality of due dates and the plurality of release times into decomposed single machine scheduling problems;
• for each single machine scheduling problem, determine job release dates, job due dates and/or job penalties based on the received operation due dates and operation release dates and/or operation penalties;
• allocate each single machine scheduling problem to a resource agent in a multi-agent system, each resource agent solving all allocated single machine scheduling problems using a genetic algorithm thereby obtaining corresponding near optimal single machine scheduling problem solutions;
• integrate all obtained near optimal single machine scheduling problem solutions into a main and global scheduling problem solution;
• and
• verify a feasibility of the main scheduling problem solution, said agents being capable of later cooperation to overcome inter-agent constraints of the main scheduling problem wherein the user interface outputs the main job shop scheduling problem solution.