Maintenance event planning and scheduling for gas turbines

• US 20060253311A1
• Filed: 09/22/2005
• Published: 11/09/2006
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Chakraborty, Amit, Yin, Watao
• Granted Patent: US 7,930,198 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• 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

Abstract

A method for scheduling a project such as the inspection and maintenance of a gas turbine utilizes a branch and bound technique for arriving at a solution. The branch and bound technique is improved by using an all-pair longest path algorithm in preprocessing to tighten the set of possible start times of the tasks. That set is further tightened by considering two-forbidden-task pairs; i.e., pairs of tasks that cannot execute at the same time due to conflicting resource needs. A hard lower bound of a branch is determined by using all-pair longest path update and two-forbidden-task pair update, reducing the need to recalculate.

Claims

1. A method for scheduling a group of tasks in a project, the tasks having interrelated temporal and resource requirements, the method comprising the steps of:

loading information regarding the temporal and resource requirements of the tasks to create a search space S;

preprocessing the search space S, including;

reducing the search space S using an all-pair longest path technique; and

applying a branch and bound technique to the preprocessed search space S to find an optimal schedule.

2. The method of claim 1, further comprising the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the steps of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using an all-pair longest path update; and

comparing the HLB with the UB.

3. The method of claim 2, wherein the step of computing an HLB comprises:

calculating a resource procurement cost incurred by tasks in b;

using all-pair lowest cost update to tighten intervals of possible start times of unscheduled tasks in b; and

deriving a non-floating time period during which each unscheduled task in b must be undergone.

4. The method of claim 1, wherein the preprocessing step further includes:

reducing the search space using a 2-forbidden task pair technique.

5. The method of claim 1, further comprising the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the steps of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using a 2-forbidden task pair update; and

comparing the HLB with the UB.

6. The method of claim 1, wherein the preprocessing step further includes the steps of:

generating a start schedule;

setting an upper bound of the start schedule;

setting a bookkeeping set from the starting schedule; and

setting a search queue.

7. The method of claim 6, wherein the branch and bound technique further includes the step of:

conducting a scatter search in the search space S to reorder the search queue.

8. The method of claim 1, wherein searching performed in the branch and bound technique comprises performing a scatter search.

9. A method for scheduling a group of tasks in a project, the tasks having interrelated temporal and resource requirements, the method comprising the steps of:

loading information regarding the temporal and resource requirements of the tasks to create a search space S;

preprocessing the search space S, including;

reducing the search space S using a 2-forbidden task pair technique; and

applying a branch and bound technique to the preprocessed search space S to find an optimal schedule.

10. The method of claim 9, further comprising the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the steps of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using a 2-forbidden task pair update; and

comparing the HLB with the UB.

11. The method of claim 10, wherein the step of computing an HLB comprises:

calculating a resource procurement cost incurred by tasks in b;

using 2-forbidden task pair update to tighten intervals of possible start

times of unscheduled tasks in b; and

deriving a non-floating time period during which each unscheduled task in b must be undergone.

12. The method of claim 9, wherein the preprocessing step further includes the steps of:

generating a start schedule;

setting an upper bound of the start schedule;

setting a bookkeeping set from the starting schedule; and

setting a search queue.

13. The method of claim 12, wherein the branch and bound technique further includes the step of:

conducting a scatter search in the search space S to reorder the search queue.

14. The method of claim 9, wherein searching performed in the branch and bound technique comprises performing a scatter search.

15. A computer program product comprising a computer readable recording medium having recorded thereon a computer program comprising code means for, when executed on a computer, instructing said computer to control steps in a method for scheduling a group of tasks in a project, the tasks having interrelated temporal and resource requirements, the method comprising the steps of:

loading information regarding the temporal and resource requirements of the tasks to create a search space S;

preprocessing the search space S, including;

reducing the search space S using an all-pair longest path technique; and

applying a branch and bound technique to the preprocessed search space S to find an optimal schedule.

16. The computer program product of claim 15, wherein the method further comprises the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the steps of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using an all-pair longest path update; and

comparing the HLB with the UB.

17. The computer program product of claim 16, wherein the step of computing an HLB comprises:

calculating a resource procurement cost incurred by tasks in b;

using all-pair lowest cost update to tighten intervals of possible start times of unscheduled tasks in b; and

deriving a non-floating time period during which each unscheduled task in b must be undergone.

18. The computer program product of claim 15, wherein the preprocessing step further includes:

reducing the search space using a 2-forbidden task pair technique.

19. The computer program product of claim 15, wherein the method further comprises the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the steps of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using a 2-forbidden task pair update; and

comparing the HLB with the UB.

20. The computer program product of claim 15, wherein the preprocessing step further includes the steps of:

generating a start schedule;

setting an upper bound of the start schedule;

setting a bookkeeping set from the starting schedule; and

setting a search queue.

21. The computer program product of claim 15, wherein the branch and bound technique further includes the step of:

conducting a scatter search in the search space S to reorder the search queue.

22. The computer program product of claim 15, wherein searching performed in the branch and bound technique comprises performing a scatter search.

23. A computer program product comprising a computer readable recording medium having recorded thereon a computer program comprising code means for, when executed on a computer, instructing said computer to control steps in a method for scheduling a group of tasks in a project, the tasks having interrelated temporal and resource requirements, the method comprising the steps of:

loading information regarding the temporal and resource requirements of the tasks to create a search space S;

preprocessing the search space S, including;

reducing the search space S using a 2-forbidden task pair technique; and

applying a branch and bound technique to the preprocessed search space S to find an optimal schedule.

24. The computer program product of claim 23, wherein the method further comprises the step of picking an upper bound UB of the search space S;

and wherein the branch and bound technique includes the step of;

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b using a 2-forbidden task pair update; and

comparing the HLB with the UB.

25. A method for scheduling a group of tasks in a project, the tasks having interrelated temporal and resource requirements, the tasks comprising a search space S, the method comprising the step of:

applying a branch and bound technique to the search space S to find an optimal schedule, the branch and bound technique including;

picking a partial schedule b from the search space S;

deriving a non-floating time period during which each unscheduled task in b must be undergone, and a floating time period during which the task is undergone only for certain start times;

distributing resource usages of the unscheduled tasks during the floating times such that total resource cost is minimized; and

setting a resulting schedule as a hard lower bound (HLB).

26. The method of claim 25, further comprising the steps of:

picking an upper bound UB of the search space S; and

comparing the HLB with the UB.