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

• US 20030139958A1
• Filed: 01/11/2002
• Published: 07/24/2003
• Est. Priority Date: 01/11/2002
• Status: Active Grant

• Current Assignee: Navitaire LLC (Amadeus Global Travel Distribution S.A.)
• Original Assignee: Accenture Global Services GmbH (Accenture PLC)
• Inventors: Thengvall, Benjamin Glover, Qi, Xiangtong
• Granted Patent: US 7,240,018 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• 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 system for rapidly generating pilot training schedules for all pilots of an entire airline, which comprises:

user communication means for receiving user requests for said pilot training schedules and input data from a user;

optimization processor means in electrical communication with said user communication means for receiving said user requests and said input data, and in response to said user requests generating optimal pilot training schedules rapidly for all pilots of said entire airline from said input data; and

data storage means in electrical communication with said optimization processor means for storing said input data, said user requests, and said optimal pilot training schedules for access by said user.

2. The system of claim 1, wherein said input data includes identification of available training resources, available training instructors, classes that need to be scheduled, a class roster for each class to be scheduled, individual student training requirements, recurrent training requirements, individual student experience and qualifications, and training curriculum information.

3. The system of claim 2, wherein said optimization processor means executes a branch and bound algorithm to generate a daily training schedule for each of said classes by determining on which calendar days training will take place.

4. The system of claim 3, wherein said optimization processor generates a mixed integer programming model of an optimizer session as follows in response to said daily training schedule, and solves said mixed integer programming model to provide detailed optimal pilot training schedules:

5. The system of claim 4, wherein said mixed integer programming model is solved through use of ILOG Concert Technology 1.0 and iLOG CPLEX 7.0.

6. The system of claim 3, wherein said branch and bound algorithm generates plural branch and bound trees which are used in repeated cycles with each tree solving a larger subset of said classes to progressively refine said daily training schedule until all of said classes have been scheduled.

7. The system of claim 6, wherein each of said plural branch and bound trees is comprised of a root node, child nodes, and leaf nodes, and said optimization processor means compares said leaf nodes of each of said plural branch and bound trees to select said optimal training schedules.

8. The system of claim 1, wherein said optimal pilot training schedules include detailed assignment of resources for each day of training for each student in each class.

9. The system of claim 4, wherein said mixed integer programming model includes the following constraints:

10. The system of claim 3, wherein said branch and bound algorithm generates plural branch and bound trees which are used in repeated cycles with each tree solving a larger subset of said classes to progressively refine said daily training schedule until allotted time for generating said daily training schedule has elapsed.

11. A method for rapidly generating pilot training schedules, which comprises the following steps:

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;

pruning from said branch and bound tree those of said plural child nodes which are infeasible;

estimating a lower bound for each of remaining child nodes of said branch and bound tree;

selecting from said remaining child nodes, child nodes having least lower bounds;

generating from said solution child nodes having least lower bounds daily student and resource schedules;

building a mixed integer programming model from said daily student and resource schedules, and from recurrent training requirements received from said user and said database, and

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

12. The method of claim 11, wherein said mixed integer programming model is as follows:

13. The method of claim 12, wherein said mixed integer programming model includes the following constraints:

14. A system for generating minimum length pilot training schedules for all pilots of an entire airline, which comprises:

a user communication interface receiving user requests and input data from a user, and status messages for informing said user;

an optimizer system in electrical communication with said user communication interface for receiving said user requests and said input data, and in response thereto rapidly generating pilot training schedules; and

a database in electrical communication with said optimizer system and having stored therein said input data, and said pilot training schedules for access by said user.