Maintenance event planning and scheduling for gas turbines
First Claim
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 dij 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 dij 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, includingusing 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
10 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 dij 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 dij 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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 dij 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 dij 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. - View Dependent Claims (7, 8, 9, 10)
-
Specification