Multi-agent system for distributed manufacturing scheduling with Genetic Algorithms and Tabu Search
First Claim
1. A computerized scheduling method stored in a memory and executed on one or more processors, the method comprising:
- decomposing a main job shop scheduling problem as a plurality of distributable single machine scheduling problems;
distributing the plurality of single machine scheduling problems to a plurality of single machine scheduling problem software agents, the software agents the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; and
integrating the plurality of near optimal single machine scheduling problem solutions obtained by each agent into a main job-shop scheduling problem solution said agents being capable of later cooperation to overcome inter-agent constraints of the main job shop scheduling problem solution; and
outputting the main job shop scheduling problem solution.
0 Assignments
0 Petitions
Accused Products
Abstract
Computerized scheduling methods and computerized scheduling systems according to exemplary embodiments. A computerized scheduling method may be stored in a memory and executed on one or more processors. The method may include defining a main multi-machine scheduling problem as a plurality of single machine scheduling problems; independently solving the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; integrating the plurality of near optimal single machine scheduling problem solutions into a main multi-machine scheduling problem solution; and outputting the main multi-machine scheduling problem solution.
-
Citations
27 Claims
-
1. A computerized scheduling method stored in a memory and executed on one or more processors, the method comprising:
-
decomposing a main job shop scheduling problem as a plurality of distributable single machine scheduling problems; distributing the plurality of single machine scheduling problems to a plurality of single machine scheduling problem software agents, the software agents the plurality of single machine scheduling problems thereby calculating a plurality of near optimal single machine scheduling problem solutions; and integrating the plurality of near optimal single machine scheduling problem solutions obtained by each agent into a main job-shop scheduling problem solution said agents being capable of later cooperation to overcome inter-agent constraints of the main job shop scheduling problem solution; and outputting the main job shop scheduling problem solution. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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. - View Dependent Claims (9, 10, 11, 12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
20. 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. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27)
-
Specification