Automated finite capacity scheduler

• US 7,505,827 B1
• Filed: 11/06/1998
• Issued: 03/17/2009
• Est. Priority Date: 11/06/1998
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Johnson, Daniel P., Boddy, Mark S.
• Primary Examiner(s): DeCady; Albert
• Assistant Examiner(s): Garland; Steven R
• Application Number:
  US09/188,399
• Time in Patent Office: 3,784 Days
• Field of Search: 700/95, 700/103, 700/97, 700 99-102, 705 7- 9, 706/62, 713/2
• US Class Current: 700/100
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

A scheduler for a finite capacity process provides a schedule based on an integrated assessment of both discrete and continuous constraints. Given a list of products to be provided, the scheduler generates a set of activities required to produce the products and identifies resources required and the discrete and continuous constraints related to such resources. Activities are resized, and timelines are established for the activities as a function of deadlines for the product delivery for which the activities are related. Resource balancing heuristics are used to redistribute resource utilization to prevent bottlenecks. Data structures are used to keep track of constraints. Both discrete and continuous constraints are defined. Separate solver engines for the discrete and continuous constraint problems modify the constraints. The data structures are used to share and propagate constraints between the two engines. Infeasibilities of meeting product delivery times are detected during the scheduling and backtracking and rescheduling of resources based on under and over utilization and availability of equivalent resources is performed.

Claims

1. A computer implemented method of scheduling orders for multiple different products or services, the method comprising:

creating a list of activities required to accomplish the orders;

modifying selected activities into sets of smaller activities; and

scheduling the activities and smaller activities based on discrete and continuous constraints, wherein the continuous constraints are related to other variables by linear mathematical relationships, and wherein separate engines process the discrete and continuous constraints and propagate additional constraints to each other to produce a schedule for the activities.

2. The method of claim 1 wherein modifying selected activities is performed as a function of integrated implications of the discrete and continuous constraints.

3. The method of claim 1 wherein modifying selected activities comprises determining if an activity is larger than a predetermined threshold.

4. The method of claim 1 wherein modifying selected activities comprises determining if an activity occurs slower than a predetermined threshold.

5. The method of claim 1 and further comprising defining discrete and continuous constraints related to the activities based on requirements of the orders.

6. The method of claim 5 wherein activities are assigned start and end times.

7. The method of claim 5 wherein activities are scheduled based on deadlines.

8. The method of claim 5 wherein the requirements of the orders comprise identification of resources required to perform the orders.

9. The method of claim 8 wherein activities are assigned resources based on a resource balancing heuristic.

10. The method of claim 1 and further comprising identifying suboptimalities during the scheduling of activities and identifying culprit activities causing the suboptimalities.

11. The method of claim 1 wherein the schedule is modified by repeating the method after removing orders already completed.

12. A computer implemented method of scheduling tasks comprising:

creating a list of activities required to accomplish the tasks;

modifying selected activities into sets of smaller activities;

scheduling the activities and smaller activities based on discrete and continuous constraints;

identifying infeasibilities during the scheduling of activities;

identifying a culprit activity when an infeasibility is identified; and

chronological backtracking to the culprit activity which resulted in an infeasibility.

13. A computer implemented method of scheduling activities comprising:

defining discrete and continuous constraints related to the activities;

representing selected scheduling decisions as discrete and continuous constraints; and

scheduling activities in accordance with integrated implications of the discrete and continuous constraints, wherein separate engines process the discrete and continuous constraints and propagate additional constraints to each other to produce a schedule for the activities.

14. The method of claim 13 and further comprising:

scheduling activities in accordance with previous scheduling decision constraints;

identifying infeasibilities during the scheduling of activities; and

scheduling activities in accordance with identified infeasibilities.

15. The method of claim 14 and further comprising:

identifying a culprit activity which resulted in an infeasibility; and

backtracking to the culprit and rescheduling the culprit activity.

16. The method of claim 15 and further comprising identifying a culprit activity which resulted in a suboptimality.

17. A computer implemented method of scheduling activities comprising:

defining discrete and continuous constraints related to the activities;

representing selected scheduling decisions as discrete and continuous constraints;

scheduling activities in accordance with integrated implications of the discrete and continuous constraints;

scheduling activities in accordance with previous scheduling decision constraints;

identifying infeasibilities during the scheduling of activities;

scheduling activities in accordance with identified infeasibilities;

identifying a culprit activity which resulted in an infeasibility; and

chronological backtracking to the culprit and rescheduling the culprit activity.

18. A machine readable medium having computer executable instructions stored thereon for causing a computer to perform a method of scheduling tasks comprising:

creating a list of activities required to accomplish the tasks;

modifying selected activities into sets of smaller activities; and

scheduling the activities and smaller activities based on discrete and continuous constraints, wherein the continuous constraints are related to other variables by linear mathematical relationships, and wherein separate engines process the discrete and continuous constraints and propagate additional constraints to each other to produce a schedule for the activities.

19. A machine readable medium having computer executable instructions stored thereon for causing a computer to perform a method of scheduling activities comprising:

defining discrete and continuous constraints related to the activities, wherein the continuous constraints are related to other variables by linear mathematical relationships;

representing selected scheduling decisions as discrete and continuous constraints; and

scheduling activities in accordance with an integrated implications of the discrete and continuous constraints, and wherein separate engines process the discrete and continuous constraints and propagate additional constraints to each other to produce a schedule for the activities.

20. A memory for access by an application program for scheduling tasks being executed on a computing system comprising:

a continuous constraint solver engine;

a discrete constraint solver engine; and

means for integrating the engines to schedule activities to accomplish the tasks taking into account both continuous constraints and discrete constraints, wherein the continuous constraints are related to other variables by linear mathematical relationships, and wherein separate engines process the discrete and continuous constraints and propagate additional constraints to each other to produce a schedule for the activities.