Maintenance event planning and scheduling for gas turbines

• US 7,930,198 B2
• Filed: 09/22/2005
• Issued: 04/19/2011
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Siemens Corp. (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Yin, Watao, Chakraborty, Amit
• Primary Examiner(s): CHOI, PETER H
• Application Number:
  US11/232,774
• Publication Number:
  US 20060253311A1
• Time in Patent Office: 2,035 Days
• Field of Search: 705/8
• US Class Current: 705/7.12
• 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 turbine maintenance project, the tasks having interrelated temporal constraints and resource requirements, the temporal constraints comprising minimum and maximum delays between tasks, the method comprising the steps of:

loading information regarding the turbine maintenance project, including the temporal constraints and resource requirements of the tasks, precedence rules on the tasks, resource price models, resource availabilities, and a resource cost objective to measure performance, to create a search space S;

in a computer processor, preprocessing the search space S, including;

creating, using the precedence rules on the tasks, an event-on-node network having nodes corresponding to the tasks;

reducing the search space S using an all-pair longest path technique, including calculating a longest path d_ij between each pair of nodes i, j in the event-on-node network considering the temporal constraints of the tasks, and removing from the search space S all schedules including a delay less than d_ij between nodes i and j;

reducing the search space S using a 2-forbidden task pair technique, including identifying, based on the resource requirements and the resource availabilities, conflicting pairs of tasks that cannot execute simultaneously because the resource availabilities are exceeded, and removing from the search space S all schedules containing simultaneous execution of the conflicting pairs of tasks; and

picking an upper bound UB of the search space S;

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

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b to evaluate the resource cost objective, including

using the resource price models, calculating resource procurement costs incurred by tasks in b;

using all-pair shortest path technique to tighten intervals of possible start times of unscheduled tasks in b;

deriving non-floating time periods during which each unscheduled task in b must be undergone; and

minimizing a total resource procurement cost of all tasks in b by adjusting start times of the unscheduled tasks in b to distribute the resource procurement costs that are incurred outside the non-floating time periods; and

removing the partial schedule b from the search space S if the HLB is greater than the UB; and

scheduling the tasks according to the 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 a 2-forbidden task pair update; and

comparing the HLB with the UB.

3. 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.

4. The method of claim 3, 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.

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

6. A computer program product comprising a non-transitory computer readable recording medium having recorded thereon a computer program comprising instructions for, when executed on a computer, instructing said computer to perform a method for scheduling a group of tasks in a turbine maintenance project, the tasks having interrelated temporal constraints and resource requirements, the temporal constraints comprising minimum and maximum delays between tasks, the method comprising the steps of:

loading information regarding the turbine maintenance project, including the temporal constraints and resource requirements of the tasks, precedence rules on the tasks, resource price models, resource availabilities, and a resource cost objective to measure performance, to create a search space S;

preprocessing the search space S, including;

creating, using the precedence rules on the tasks, an event-on-node network having nodes corresponding to the tasks;

reducing the search space S using an all-pair longest path technique, including calculating a longest path d_ij between each pair of nodes i, j in the event-on-node network considering the temporal constraints of the tasks, and removing from the search space S all schedules including a delay less than d_ij between nodes i and j;

reducing the search space S using a 2-forbidden task pair technique, including identifying, based on the resource requirements and the resource availabilities, conflicting pairs of tasks that cannot execute simultaneously because the resource availabilities are exceeded, and removing from the search space S all schedules containing simultaneous execution of the conflicting pairs of tasks; and

picking an upper bound UB of the search space S;

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

picking a partial schedule b from the search space S;

computing a hard lower bound HLB of the partial schedule b to evaluate the resource cost objective, including

using the resource price models, calculating resource procurement costs incurred by tasks in b;

using all-pair shortest path technique to tighten intervals of possible start times of unscheduled tasks in b;

deriving non-floating time periods during which each unscheduled task in b must be undergone; and

minimizing a total resource procurement cost of all tasks in b by adjusting start times of the unscheduled tasks in b to distribute the resource procurement costs that are incurred outside the non-floating time periods; and

removing the partial schedule b from the search space S if the HLB is greater than the UB; and

scheduling the tasks according to the optimal schedule.

7. The computer program product of claim 6, 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.

8. The computer program product of claim 6, 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.

9. The computer program product 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.

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