System to resolve scheduling constraints

• US 7,805,326 B2
• Filed: 12/26/2006
• Issued: 09/28/2010
• Est. Priority Date: 11/15/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Scheuer, Tobias
• Primary Examiner(s): Jeanty; Romain
• Assistant Examiner(s): WALKER III, GEORGE H
• Application Number:
  US11/645,469
• Publication Number:
  US 20080115142A1
• Time in Patent Office: 1,372 Days
• Field of Search: 705/8, 705/9
• US Class Current: 705/7.26
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work

Abstract

A system may associate a first activity of a group of activities with a first resource, a first start time on the first resource, and a first end time on the first resource, associate a second activity of the group of activities with a second resource, a second start time on the second resource, and a second end time on the second resource, and resolve a maximum constraint of the first activity and a maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource. Further aspects may include determination of one or more maximum constraints of the first activity, determination of one or more maximum constraints of the second activity, and determination that at least one of the one or more maximum constraints of the first activity and the one or more maximum constraints of the second activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource.

Claims

1. A method, comprising:

associating, by a processor, a first activity of a group of activities with a first resource, a first start time on the first resource, and a first end time on the first resource, wherein associating the first activity with the first resource comprises associating the first activity with the first resource based on one or more minimum constraints of the first activity;

associating, by a processor, a second activity of the group of activities with a second resource, a second start time on the second resource, and a second end time on the second resource, wherein the second activity is preceded by the first activity in a desired order of execution and wherein associating the second activity with the second resource comprises associating the second activity with the second resource based on one or more minimum constraints of the second activity;

determining, before the association of the second activity with the second resource, that a first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource;

determining, before the association of the second activity with the second resource, that a second maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and the association of the second activity with the second resource;

resolving, by a processor, the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource;

wherein resolving the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises;

determining that the first maximum constraint of the first activity is violated after the association of the first activity with the first resource and before the association of the second activity with the second resource;

disassociating the first activity from the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

re-associating the first activity with the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

resolving, by a processor, the second maximum constraint of the first activity and a maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource.

2. A method according to claim 1, further comprising:

associating, by a processor, a third activity of the group of activities with the first resource, a third start time on the first resource, and a third end time on the first resource;

determining, by a processor, one or more maximum constraints of the third activity;

determining, by a processor, that one of the one or more maximum constraints of the third activity should be resolved before all activities of the group are associated with their respective resources;

determining, by a processor, that another one of the one or more maximum constraints of the third activity should be resolved after all activities of the group are associated with their respective resources;

resolving, by a processor, the one of the one or more maximum constraints of the third activity before all activities of the group are associated with their respective resources; and

resolving, by a processor, the other one of the one or more maximum constraints of the third activity after all activities of the group are associated with their respective resources.

3. A method according to claim 1, wherein the first resource and the second resource are the same resource.

4. A method according to claim 1, wherein disassociating the first activity from the first resource comprises:

disassociating the first activity from the first resource in response to determining that the maximum constraint of the second activity is violated.

5. A method according to claim 4, wherein re-associating the first activity with the first resource, the first start time on the first resource, and the first end time on the first resource comprises:

re-associating the first activity with the first resource after the disassociating the first activity from the first resource.

6. A method according to claim 1, wherein resolving the second maximum constraint of the first activity and the maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource comprises:

determining that the maximum constraint of the second activity is violated;

disassociating the first activity from the first resource; and

disassociating all successor activities of the first activity from their respective resources.

7. A method according to claim 6, the method further comprising:

re-associating, by a processor, the first activity with the first resource, the first start time on the first resource, and the first end time on the first resource;

re-associating, by a processor, the second activity with the second resource, a third start time on the second resource, and a third end time on the second resource; and

resolving, by a processor, the second maximum constraint of the first activity and the maximum constraint of the second activity after the re-association of the first activity with the first resource and the re-association of the second activity with the second resource.

8. A method according to claim 1, wherein determining that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises:

determining that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource if the first maximum constraint is a binary type maximum constraint.

9. A computer-readable medium storing program code executable by one or more processors to result in a method comprising:

associating a first activity of a group of activities with a first resource, a first start time on the first resource, and a first end time on the first resource, wherein associating the first activity with the first resource comprises associating the first activity with the first resource based on one or more minimum constraints of the first activity;

associating a second activity of the group of activities with a second resource, a second start time on the second resource, and a second end time on the second resource, wherein the second activity is preceded by the first activity in a desired order of execution and wherein associating the second activity with the second resource comprises associating the second activity with the second resource based on one or more minimum constraints of the second activity;

determining, before the association of the second activity with the second resource, that a first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource;

determining, before the association of the second activity with the second resource, that a second maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and the association of the second activity with the second resource;

resolving the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource;

wherein resolving the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises;

determining that the first maximum constraint of the first activity is violated after the association of the first activity with the first resource and before the association of the second activity with the second resource;

disassociating the first activity from the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

re-associating the first activity with the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

resolving the second maximum constraint of the first activity and a maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource.

10. A medium according to claim 9, the medium further comprising:

associating a third activity of the group of activities with the first resource, a third start time on the first resource, and a third end time on the first resource;

associating one or more maximum constraints of the third activity;

determining that one of the one or more maximum constraints of the third activity should be resolved before all activities of the group are associated with their respective resources;

determining that another one of the one or more maximum constraints of the third activity should be resolved after all activities of the group are associated with their respective resources;

resolving the one of the one or more maximum constraints of the third activity before all activities of the group are associated with their respective resources; and

resolving the other one of the one or more maximum constraints of the third activity after all activities of the group are associated with their respective resources.

11. A medium according to claim 9, wherein the first resource and the second resource are the same resource.

12. A medium according to claim 9, wherein resolving the second maximum constraint of the first activity and the maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource comprises:

determining that the maximum constraint of the second activity is violated;

disassociating the first activity from the first resource; and

disassociating all successor activities of the first activity from their respective resources.

13. A medium according to claim 12, the medium further comprising:

re-associating the first activity with the first resource, the first start time on the first resource, and the first end time on the first resource;

re-associating the second activity with the second resource, a third start time on the second resource, and a third end time on the second resource; and

resolving the second maximum constraint of the first activity and the maximum constraint of the second activity after the re-association of the first activity with the first resource and the re-association of the second activity with the second resource.

14. A medium according to claim 9, wherein determining that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises:

determining that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource if the first maximum constraint is a binary type maximum constraint.

15. A system comprising:

a database of transactional objects stored in main memory, the database comprising activity objects, order objects and resource objects;

one or more processors in communication with the database, the one or more processors to;

associate a first activity of a group of activities with a first resource, a first start time on the first resource, and a first end time on the first resource, wherein association of the first activity with the first resource comprises association of the first activity with the first resource based on one or more minimum constraints of the first activity;

associate a second activity of the group of activities with a second resource, a second start time on the second resource, and a second end time on the second resource, wherein the second activity is preceded by the first activity in a desired order of execution and wherein association of the second activity with the second resource comprises association of the second activity with the second resource based on one or more minimum constraints of the second activity;

determine, before the association of the second activity with the second resource, that a first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource;

determine, before the association of the second activity with the second resource, that a second maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and the association of the second activity with the second resource;

resolve the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource;

wherein resolution of the first maximum constraint of the first activity after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises;

determination that the first maximum constraint of the first activity is violated after the association of the first activity with the first resource and before the association of the second activity with the second resource;

disassociation of the first activity from the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

re-association of the first activity with the first resource after the association of the first activity with the first resource and before the association of the second activity with the second resource; and

resolve the second maximum constraint of the first activity and a maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource.

16. A system according to claim 15, the one or more processors further to:

associate a third activity of the group of activities with the first resource, a third start time on the first resource, and a third end time on the first resource;

determine one or more maximum constraints of the third activity;

determine that one of the one or more maximum constraints of the third activity should be resolved before all activities of the group are associated with their respective resources;

determine that another one of the one or more maximum constraints of the third activity should be resolved after all activities of the group are associated with their respective resources;

resolve the one of the one or more maximum constraints of the third activity before all activities of the group are associated with their respective resources; and

resolve the other one of the one or more maximum constraints of the third activity after all activities of the group are associated with their respective resources.

17. A system according to claim 15, wherein the first resource and the second resource are the same resource.

18. A system according to claim 15, wherein resolution of the second maximum constraint of the first activity and the maximum constraint of the second activity after the association of the first activity with the first resource and the association of the second activity with the second resource comprises:

determination that the maximum constraint of the second activity is violated;

disassociation of the first activity from the first resource; and

disassociation of all successor activities of the first activity from their respective resources.

19. A system according to claim 18, the database further to:

re-associate the first activity with the first resource, the first start time on the first resource, and the first end time on the first resource;

re-associate the second activity with the second resource, a third start time on the second resource, and a third end time on the second resource; and

resolve the second maximum constraint of the first activity and the maximum constraint of the second activity after the re-association of the first activity with the first resource and the re-association of the second activity with the second resource.

20. A system according to claim 15, wherein determination that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource comprises:

determination that the first maximum constraint of the first activity should be resolved after the association of the first activity with the first resource and before the association of the second activity with the second resource if the first maximum constraint is a binary type maximum constraint.