System and method for rapid generation of minimum length pilot training schedules

• US 8,447,646 B2
• Filed: 03/30/2007
• Issued: 05/21/2013
• Est. Priority Date: 01/11/2002
• Status: Expired due to Fees

• Current Assignee: Navitaire LLC (Amadeus Global Travel Distribution S.A.)
• Original Assignee: Accenture Global Services Limited (Accenture PLC)
• Inventors: Thengvall, Benjamin Glover, Qi, Xiangtong
• Primary Examiner(s): Rines, David
• Application Number:
  US11/694,414
• Publication Number:
  US 20070166692A1
• Time in Patent Office: 2,244 Days
• Field of Search: None
• US Class Current: 705/7.42
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/109 Time management, e.g. calendars, reminders, meetings or time accounting
• CPC Class Codes: G06Q 10/1097 Task assignment
• CPC Class Codes: G06Q 50/2057 Career enhancement or continuing education service

Abstract

A system for rapidly generating minimum length pilot training schedules which uses a branch and bound, and a mixed integer programming model with constraints to produce student and resource schedules at a device period level for all pilots of an airline.

Claims

1. A computer-implemented method comprising:

receiving fleet training information including class, curriculum, resource, student, and instructor information from a user and a database;

building branch and bound trees having a root node and plural child nodes each representing an alternative partial schedule for one or more pilot training classes, wherein, for a particular node that defines a partial schedule for all pilot training classes through a particular day, a child node of the particular node defines a partial schedule of all pilot training classes through a day after the particular day, and wherein said branch and bound trees are used in repeated cycles until a predetermined processing time limit is exhausted;

for each cycle;

(i) pruning from said branch and bound trees those of said plural child nodes which violate logical rules pertaining to said pilot training classes;

(ii) estimating a lower bound for each of remaining child nodes of said branch and bound trees, said lower bound providing an estimate for a solution that can be found in any descendant of that node;

(iii) selecting from said remaining child nodes, solution child nodes having least lower bounds;

(iv) generating from said solution child nodes having least lower bounds daily student and resource schedules for a progressively greater number of said pilot training classes in each cycle; and

(v) determining whether additional processing time is available;

building, by one or more computers, a mixed integer programming model from said daily student and resource schedules generated from said solution child nodes from said branch and bound trees, and from recurrent training requirements received from said user and said database, wherein said mixed integer programming model comprises a cost assignment of a class group and a balancing cost,

solving said mixed integer programming model to provide detailed hourly student and resource schedules at a device period level, and provide time for recurrent training, and

outputting said detailed hourly student and resource schedules for dissemination.

2. The method of claim 1, wherein the mixed integer programming model comprises a product of a first binary variable and the cost assignment of a class group and a product of a second binary variable and the balancing costs.

3. The method of claim 2, wherein said mixed integer programming model is expressed as:

4. The method of claim 3, wherein the mixed integer programming model includes the following constraints:

5. A system comprising:

one or more computers; and

a non-transitory computer-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving fleet training information including class, curriculum, resource, student, and instructor information from a user and a database;

building branch and bound trees having a root node and plural child nodes each representing an alternative partial schedule for one or more pilot training classes, wherein, for a particular node that defines a partial schedule for all pilot training classes through a particular day, a child node of the particular node defines a partial schedule of all pilot training classes through a day after the particular day, and wherein said branch and bound trees are used in repeated cycles until a predetermined processing time limit is exhausted;

for each cycle;

(i) pruning from said branch and bound trees those of said plural child nodes which violate logical rules pertaining to said pilot training classes;

(ii) estimating a lower bound for each of remaining child nodes of said branch and bound trees, said lower bound providing an estimate for a solution that can be found in any descendant of that node;

(iii) selecting from said remaining child nodes, solution child nodes having least lower bounds;

(iv) generating from said solution child nodes having least lower bounds daily student and resource schedules for a progressively greater number of said pilot training classes in each cycle; and

(v) determining whether additional processing time is available;

building a mixed integer programming model from said daily student and resource schedules generated from said solution child nodes from said branch and bound trees, and from recurrent training requirements received from said user and said database, wherein said mixed integer programming model comprises a cost assignment of a class group and a balancing cost,

solving said mixed integer programming model to provide detailed hourly student and resource schedules at a device period level, and provide time for recurrent training, and

outputting said detailed hourly student and resource schedules for dissemination.

6. The system of claim 5, wherein the mixed integer programming model comprises a product of a first binary variable and the cost assignment of a class group and a product of a second binary variable and the balancing costs.

7. The system of claim 6, wherein said mixed integer programming model is expressed as:

8. The system of claim 7, wherein the mixed integer programming model includes the following constraints:

9. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving fleet training information including class, curriculum, resource, student, and instructor information from a user and a database;

building branch and bound trees having a root node and plural child nodes each representing an alternative partial schedule for one or more pilot training classes, wherein, for a particular node that defines a partial schedule for all pilot training classes through a particular day, a child node of the particular node defines a partial schedule of all pilot training classes through a day after the particular day, and wherein said branch and bound trees are used in repeated cycles until a predetermined processing time limit is exhausted;

for each cycle;

(i) pruning from said branch and bound trees those of said plural child nodes which violate logical rules pertaining to said pilot training classes;

(ii) estimating a lower bound for each of remaining child nodes of said branch and bound trees, said lower bound providing an estimate for a solution that can be found in any descendant of that node;

(iii) selecting from said remaining child nodes, solution child nodes having least lower bounds;

(iv) generating from said solution child nodes having least lower bounds daily student and resource schedules for a progressively greater number of said pilot training classes in each cycle; and

(v) determining whether additional processing time is available;

building a mixed integer programming model from said daily student and resource schedules generated from said solution child nodes from said branch and bound trees, and from recurrent training requirements received from said user and said database, wherein said mixed integer programming model comprises a cost assignment of a class group and a balancing cost,

solving said mixed integer programming model to provide detailed hourly student and resource schedules at a device period level, and provide time for recurrent training, and

outputting said detailed hourly student and resource schedules for dissemination.

10. The computer storage medium of claim 9, wherein the mixed integer programming model comprises a product of a first binary variable and the cost assignment of a class group and a product of a second binary variable and the balancing costs.

11. The computer storage medium of claim 10, wherein said mixed integer programming model is expressed as:

12. The computer storage medium of claim 11, wherein the mixed integer programming model includes the following constraints: