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

• US 8,606,386 B2
• Filed: 03/11/2011
• Issued: 12/10/2013
• Est. Priority Date: 03/12/2010
• Status: Expired due to Fees

• Current Assignee: Ana Maria Dias Medureira Pereira
• Original Assignee: Ana Maria Dias Medureira Pereira
• Inventors: Pereira, Ana Maria Dias Medureira
• Primary Examiner(s): PATEL, RAMESH B
• Application Number:
  US13/046,346
• Publication Number:
  US 20110224816A1
• Time in Patent Office: 1,005 Days
• Field of Search: 700 99-104, 705 712- 713, 705 722- 728, 718100-104
• US Class Current: 700/100
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32333 Use of genetic algorithm
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 50/04 Manufacturing
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/30 Computing systems specially adapted for manufacturing
• CPC Class Codes: Y02P 90/80 Management or planning

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.

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.

2. The computerized scheduling method of claim 1, wherein the main job shop scheduling problem is a job shop scheduling problem (JSSP), an extended job shop scheduling problem (EJSSP), a flexible job-shop scheduling problem (FJSSP), an open-shop scheduling problem (OSSP) or a flow shop scheduling problem (FSSP).

3. The computerized scheduling method of claim 1, wherein the plurality of single machine scheduling problems are solved using or a genetic algorithm.

4. The computerized scheduling method of claim 1, further comprising:

verifying a feasibility of the main job shop scheduling problem solution.

5. The computerized scheduling method of claim 4, wherein the verifying of the feasibility of the main job shop scheduling problem solution includes verifying near optimal solutions terminate with a local optimum optimum or a near-optimal solution.

6. The computerized scheduling method of claim 4, wherein if the main job shop scheduling problem solution is not feasible, a repairing mechanism is applied to the main job shop scheduling problem solution.

7. The computerized scheduling method of claim 1, wherein said cooperation comprises,

modifying at least one of the near optimal single machine scheduling problem solutions;

and

repeating the operations of independently solving the plurality of single machine scheduling problems, including the modified at least one near optimal single machine scheduling problem, and integrating the plurality of near optimal single machine scheduling problem solutions into the main job shop scheduling problem solution.

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.

9. The computerized scheduling method of claim 8, wherein the main job shop scheduling problem is a job shop scheduling problem (JSSP), an extended job-shop scheduling problem (EJSSP), or a flow shop scheduling problem (FSSP), a flexible job-shop scheduling problem (FJSSP), or an open-shop scheduling problem (OSSP).

10. The computerized scheduling method of claim 8, wherein the verifying of the feasibility of the main job shop scheduling problem solution includes verifying near optimal solutions terminate with a local optimum or near optimal schedule.

11. The computerized scheduling method of claim 8, wherein if the main job shop scheduling problem solution is not feasible, a repairing mechanism is applied to the main job shop scheduling problem solution.

12. The computerized scheduling method of claim 8,

wherein said resource agents cooperate by modifying at least one of the near optimal single machine scheduling problems;

and

repeating the operations of independently solving the plurality of single machine scheduling problems, including the modified at least one near optimal single machine scheduling problem, and integrating the plurality of near optimal single machine scheduling problem solutions into the main job shop scheduling problem solution.

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.

14. The computerized scheduling system of claim 13, wherein the main job shop scheduling problem is a job-shop scheduling problem (JSSP), an extended job-shop scheduling problem (EJSSP), a flow shop scheduling problem (FSSP), a flexible job-shop scheduling problem (FJSSP), or an open-shop scheduling problem (OSSP).

15. The computerized scheduling system of claim 13, wherein the single machine scheduling problems are solved using a genetic algorithm.

16. The computerized scheduling system of claim 13, wherein the hybrid scheduling module logic is further configured to:

verify a feasibility of the main job shop scheduling problem solution.

17. The computerized scheduling system of claim 16, wherein the verifying of the feasibility of the main job shop scheduling problem solution includes verifying near optimal solutions terminate with a local optimum.

18. The computerized scheduling system of claim 16, wherein if the main job shop scheduling problem solution is not feasible, a repairing mechanism is applied to the main job shop scheduling problem solution.

19. The computerized scheduling system of claim 13, wherein the hybrid scheduling module logic is further configured to:

modify at least one of the near optimal single machine scheduling problem solutions; and

repeat the operations of independently solving the plurality of single machine scheduling problems, including the modified at least one near optimal single machine scheduling problem, and integrating the plurality of near optimal single machine scheduling problem solutions into the main job shop scheduling problem solution.

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.

21. The computerized scheduling system of claim 20, wherein the main job shop scheduling problem is a job shop scheduling problem (JSSP), an extended job-shop scheduling problem (EJSSP), a flow shop scheduling problem (FSSP), a flexible job-shop scheduling problem (FJSSP), or an open-shop scheduling problem (OSSP).

22. The computerized scheduling system of claim 20, wherein the verifying of the feasibility of the main job shop scheduling problem solution includes verifying near optimal solutions terminate with a local optimum or near optimal solution.

23. The computerized scheduling system of claim 20, wherein if the main job shop scheduling problem solution is not feasible, a repairing mechanism is applied to the main job shop scheduling problem solution.

24. The computerized scheduling system of claim 20, wherein said resource agents cooperate by:

modifying at least one of the near optimal single machine scheduling problems; and

repeating the operations of independently solving the plurality of single machine scheduling problems, including the modified at least one near optimal single machine scheduling problem, and integrating the plurality of near optimal single machine scheduling problem solutions into the main job shop scheduling problem solution.

25. The computerized scheduling system of claim 24, wherein said resource agents coordinate their respective local optimization efforts and knowledge using self-organized behavior.

26. The computerized scheduling system of claim 25, wherein the hybrid scheduling module is further configured to employ meta-heuristics as optimization techniques which are adapted to deal with dynamic problems including reusing and adapting individuals/populations in accordance with the dynamism of an associated manufacturing system.

27. The computerized scheduling system of claim 26, further comprising:

computerized scheduling self-organized modules, including self-configuration and self-parameterization modules, associated with the meta-heuristics that allows adapting to a situation being considered related to problem dimension and neighborhood/population size.