Method and system for timetabling using pheromone and hybrid heuristics based cooperating agents

• US 20060184470A1
• Filed: 08/26/2005
• Published: 08/17/2006
• Est. Priority Date: 11/24/2004
• Status: Active Grant

• Current Assignee: Nanyang Polytechnic
• Original Assignee: Nanyang Polytechnic
• Inventors: Zhu, Chunbao
• Granted Patent: US 7,447,669 B2
• Time in Patent Office: Days
• US Class Current: 706/16
• CPC Class Codes: G06N 3/00 Computing arrangements based on biological models
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]

Abstract

The present invention provides a timetabling system based on an improved ant colony optimization using pheromone and hybrid heuristics based cooperating agents. The timetabling system can provide an optimal timetable solution for a timetable problem that consists of a plurality of activities, each activity being scheduled to a start time within a planning period and being allocated all required resources from a plurality of sets of resources. In one aspect of the present invention, the timetabling system comprises an electronic device having a memory capacity that contains a storage medium, and a timetabling module being implemented in the electronic device. The present invention also provides a timetabling method based on an improved ant colony optimization by using pheromone and hybrid heuristics based cooperating agents to obtain an optimal timetable solution for a timetable problem that consists of a plurality of activities, each activity being scheduled into a start time within a planning period and being allocated all required resources from a plurality of sets of resources.

Claims

1. A timetabling system based on an improved ant colony optimization using pheromone and hybrid heuristics based cooperating agent, wherein the timetabling system can provide an optimal timetable solution for a timetable problem that consists of a plurality of activities, each activity being scheduled to a start time within a planning period and being allocated all required resources from a plurality of sets of resources, said timetabling system comprising:

an electronic device having a memory capacity that contains a storage medium, wherein the storage medium stores the information of the timetable problem including the plurality of activities, the time slots within the planning period, and the plurality of sets of resources; and

a timetabling module being implemented in the electronic device;

wherein the timetabling module comprises a source graph constructor for constructing the source graph for the timetable problem;

wherein the source graph consists of a plurality of activity nodes representing the activities, a plurality of resource nodes representing the resources, and a plurality of time nodes that are associated with the plurality of resource nodes, thereby the plurality of resource nodes and the time nodes form a multi-resource-time-space, i.e., the source graph; and

wherein the timetabling module comprises a timetable solution searching engine performing timetable solution searching cycles on the source graph to thereby determine an optimal timetable solution.

2. The timetabling system of claim 1, wherein the timetable solution searching cycles are based upon local searching heuristic and global pheromone updating rules, and carried out by pheromone and hybrid heuristics based cooperating agents.

3. The timetabling system of claim 2, wherein the local searching heuristic rules include a probability function of resource by which the searching agents choose a possible resource assignment cluster, wherein the probability function of resource may be represented by P^ak_z=f(τ

^ak_z, CATP_z, CSr^ak_z);

wherein each possible assignment cluster in indexed as z, τ

^ak_z is the amount of trails present on a link, CATP₂ reflects the number of CATPs available and location of the CATP within the planning period, and CSr^ak_z, the evaluation of constraints imposed, including generic constraints which are imposed to all activities and specific constraints which are imposed to this activity only; and

a probability function of time by which the searching agents choose an optimal CATP from which the start time for activity a_k is derived, wherein the probability function of time may be represented by P^ak_y=f(τ

^ak_y, CATP_y, CSt^ak_y);

wherein τ

^ak_y is the amount of trails presented on a link from the virtual node T_ak to the CATPs, CATP_y reflects the number of CATPs available and location of the CATP within the planning period, and CSt^ak_y the evaluation of time schedule related constraints imposed, including generic constraints which are imposed to all activities and specific constraints which are imposed to this activity only.

4. The timetabling system of claim 1, wherein the source graph comprises a plurality of graph clusters, wherein each graph cluster is comprised of an activity node, a plurality of resources nodes, and a plurality of time nodes that are associated with the activity node and the resources nodes.

5. The timetabling system of claim 3, wherein each of the graph clusters comprises a plurality of possible assignment clusters, each of the possible assignment clusters representing a combination of resource allocation and time node scheduling arrangement for the activity of the graph cluster.

6. The timetabling system of claim 1, wherein the source graph constructor comprises an editor for editing the information required for the construction of the source graph, the information including constraints, time slot booking and pre-scheduled activities associated with the plurality of activity nodes, the plurality of resource nodes and the plurality of time nodes.

7. The timetabling system of claim 1, wherein the source graph constructor comprises a solution search definer for defining one or more criteria for the timetable solution searching cycles and activating one or more constraints being imposed for timetable solutions.

8. The timetabling system of claim 1, wherein the hybrid heuristics comprise:

activity ranking heuristic;

multiple resource-time-space manipulation heuristic;

constraint based reasoning;

probability based decision-making; and

optimization heuristic.

9. The timetabling system of claim 8, wherein the activity ranking heuristic may be used for ranking the plurality of activity nodes so that the most difficult activity is scheduled first, thereby the activity nodes are listed in a ranked order in the source graph.

10. The timetabling system of claim 8, wherein the multiple resource-time-space manipulation heuristic may be used for analysing available time periods for said activity.

11. The timetabling system of claim 8, wherein the multiple resource-time-space manipulation heuristic may be used for analyzing common available time periods among a plurality of resources required by one of said plurality activities.

12. The timetabling system of claim 1, wherein the local searching heuristic comprises:

a trail intensity factor;

a common available time period factor; and

a constraint evaluation factor.

13. The timetabling system of claim 12, wherein the constraint evaluation factor is based on the satisfaction level of one or more constraints imposed on the timetabling problem.

14. The timetabling system of claim 12, wherein the trail intensity factor, the common available time period factor and the constraint evaluation factor are adapted in a probability function for the searching agent to choose an optimal possible assignment cluster for the activity.

15. The timetabling system of claim 1, wherein the timetable solution searching engine is further adapted to provide m pheromone and hybrid cooperating agents for searching timetable solutions;

wherein the pheromone and hybrid cooperating agents search for the optimal timetable solution on the source graph based on the probability function.

16. The timetabling system of claim 1, further comprising a user input interface that allows the user to input information that specifies the time table problem;

wherein the information includes details of the activities, the resources requirements, constraints, and one or more optimisation criteria for the timetable solution.

17. A timetabling method based on an improved ant colony optimisation by using pheromone and hybrid heuristics based cooperating agents to obtain an optimal timetable solution for a timetable problem that consists of a plurality of activities, each activity being scheduled into a time slot within a planning period and being allocated all required resources from a plurality of sets of resources, said timetabling method comprising:

constructing a source graph having a plurality of activity nodes representing the activities, a plurality of resource nodes representing the resources, and a plurality of time nodes that are associated with the plurality of resource nodes, thereby the plurality of resource nodes and the time nodes form a multi-resource-time-space, i.e., the source graph;

initializing one or more searching parameters for one or more searching agents; and

performing timetable solution searching cycles on said source graph for each of said one or more searching agents to determine the optimal timetable solution.

18. The timetabling method of claim 17, wherein said step of constructing the source graph comprises:

retrieving data associated with said plurality of activity nodes, said plurality of resources nodes and said plurality of time nodes;

constructing said source graph, said source graph having a plurality of graph clusters, each of said graph clusters is associated with one of said plurality activity nodes, each of said graph cluster having a plurality of possible assignment clusters; and

identifying said constraints that are activated.

19. The timetabling method of claim 17, wherein said initialising step comprises defining a predetermined number of cooperating agents.

20. The timetabling method of claim 17, wherein said step of performing search cycles comprises setting a plurality of cycle parameters for searching agents, said plurality of cycle parameters being stored in a common storage medium.

21. The timetabling method of claim 20, wherein said step of performing search cycles further comprises placing a predetermined number of cooperating agents at an initial activity node, said initial node being the first activity node of the ranked activity list.

22. The timetabling method of claim 21, wherein said placing step comprises:

clearing one or more lists of scheduled activity IDs in an agent object, each of said lists of scheduled activity IDs being respectively associated with each of said cooperating agents;

clearing one or more lists of confirmed assignment cluster IDs in the agent object, each of said confirmed assignment cluster IDs representing a timetable solution searched by each of said cooperating agents; and

entering said initial activity node ID into each of said list of scheduled activity IDs.

23. The timetabling method of claim 21, wherein said step of performing search cycles further comprises:

selecting a cooperating agent from said searching agents;

choosing a possible assignment cluster for the selected cooperating agent based on a probability function; and

repeating said selecting and said choosing for remaining cooperating agents.

24. The timetabling method of claim 23, wherein said repeating step comprises adding said scheduled activity node ID to said list of scheduled activity IDs.

25. The timetabling method of claim 23, wherein said step of performing search cycles further comprises:

storing said timetable solution in form of list of the confirmed assignment clusters.

26. The timetabling method of claim 25, wherein said step of performing search cycles further comprises:

evaluating said timetable solution to determine whether to update a cycle parameter of said plurality of cycle parameters, said cycle parameter corresponding to a best path for a searching cycle.

27. The timetabling method of claim 26, wherein said step of performing search cycles further comprises:

checking whether there is another cooperating agent for the steps of selecting, choosing, and repeating.

28. The timetabling method of claim 27, wherein said step of performing search cycles further comprises:

updating trails on the searching paths using quantity of trail substance per unit of length of one or more stored valid timetable solution.

29. The timetabling method of claim 28, wherein said step of performing search cycles further comprises:

computing trail intensity for every chosen possible assignment clusters of each of said stored valid timetable solutions searched by m agents.

30. The timetabling method of claim 29, wherein said step of performing search cycles further comprises:

outputting said best timetable solution.