Preferential bidding system
Encyclopedia
Preferential bidding system, or PBS, is a computer program providing Crew scheduling
a method of solving airlines workforce schedules consisting of specific flights and certain qualified crew members while allowing those crew members to request periodic work schedules using weighted preferences. The solution must be as efficient as possible while respecting crew member preferences, honoring seniority, conforming regulations, and operation coverage requirements.
The real challenge for PBS is that it tries to solve two innately conflicted goals, honoring preferences without violating seniority and awarding all pairings.
A somewhat similar interactive Preference Request System offered by Kernel Software is used by Lufthansa
. It does not build complete schedules as does the Crewing Solutions PBS.
”Kernel Software strongly disagrees with this statement. It also thinks that Wikipedia is not the appropriate place for such discussions, and refers the interested reader of PBS to its web site for detailed information about this specific Crewing Solution PBS”.
Mr. Boegner is an expert in Heuristic algorithms. He is respected worldwide and regarded as the "Father of PBS" having introduced the concept in the 70's and eventually implemented in SmartPref, the Crewing Solutions product. There is competing school of thought that Linear Logic
is the best approach to solving the "problem" efficiently. The company SBS, he headed, installed over 100 scheduling systems with airlines. SBS was eventually sold to Boeing
.
This dynamic real-time PBS uses heuristic algorithm running as a hosted Web application
offers live current status of other crew members bids during the bidding process. A crew member designates their preferences, both globally and specifically, based on seeing real availability at that moment, at their seniority and submits a "Bid" for trips and work days. The PBS then assesses these new preferences and immediately builds a new schedule/solution, and presents this in the web based GUI
to any viewing crew member. That solution combines a bidding crew member's preferences with the existing data to create the pairings and to generate the best quality crewing solution available at the time they bid. The PBS attempts to determine what is in the bidders best interest based on those preferences previously input and continues to consider all crew member preferences throughout the remaining bidding window.
As bidders continue to enter bids, the schedule begins to take shape. In the LIVE PBS environment a crew member can return to view the status of their choices at any time. They can elect to change their preferences and resubmit them if the environment has changed such that they now wish to try to improve their situation. During the bidding process, in order to have a realistic line, crew member has to constantly adjust his bids until all his senior crew members finalize their bids. Some crew members will come back later after bidding and see a less desirable line mainly due to overriding conflicts with the senior crew members. In these cases the bidding crew member must change his preferences until he bids what he CAN get and until he gets a line which is also compatible with the data at hand by compromising his interests.
The interactive PBS gives the problem of solving conflicted interests to crew members which leads to a much simpler design in system in comparison to a conventional PBS. The resulting bid is considered optimal in that the bid preference parameters are the most accurate and efficient with respect to constraints and preferences at the present state of the solution and the seniority of the crew member. However, at the beginning of the bid period even before choices or bids are made, a reliable initial base solution must be generated from the standby or default bids, of each crew member. Although at this initial stage, the results are far from real, in the end when every one submits their bids, the results will become realistic.
Without a LIVE PBS's interactive recalculation during the bid period, if crew members bid for certain pairings and/or days off heavily over others, at the end of the bid period either an advanced, time consuming algorithm needs to be implemented to solve the resultant conflicts automatically, or manual manipulation is used to fill the "open time" (unassigned pairings).
With the live interactive PBS, it only offers "left over" pairings to crew members and naturally forces the crew members to cover them with the advantage knowing of what their schedule will likely be.
s used may be very different and usually lead to very different results and satisfactions. In addition, the user interfaces that provided for crew members to enter the preferences are also very different from vendor to vendor. The evaluation of the PBS products and the negotiation between the management and crew members are the most important and critical steps of a successful implementation of the PBS.
Crew scheduling
Crew scheduling is the process of assigning crews to operate transportation systems, such as rail lines or aircraft.- Complex :Most transportation systems use software to manage the crew scheduling process. Crew scheduling becomes more and more complex as you add variables to the problem...
a method of solving airlines workforce schedules consisting of specific flights and certain qualified crew members while allowing those crew members to request periodic work schedules using weighted preferences. The solution must be as efficient as possible while respecting crew member preferences, honoring seniority, conforming regulations, and operation coverage requirements.
Pairings
Work schedules in the airlines industry must cover not just a shift or a day, as workers in other industries might. Airlines work schedules consist of assignments called "crew pairings" or simply "pairings", which is a sequence of flights or legs that starts and then ends at the same domicile. Parings are usually created by another computer program called pairing optimizer.Bidding and Line
The process of requesting a certain schedule is called "bidding". Generally this is done on a monthly basis. The monthly schedule called "line" which a crew member gets will consist of a series of "pairings". Each month the airlines crew planning sets the new pairings due to new locations being added or removed, new times, or changes in the aircraft flown. These new pairings are then made available for assignment or bidding. In the United States, crew members are often working under a union's collective bargaining agreement, and sometimes including non-union workplaces, seniority is used to give senior crew member the right to override junior crew member requests. A line itself must also satisfy legal and contractual constraints. Ideally it should also satisfy the crew members choices and preferences.Constraints
Each month, airlines crew planning must generate legal crewing solutions. These crewing solutions strive to achieve a minimum-cost of operation by matching specific aircraft, the routes they fly and crew pairings in a manner that each leg is covered by one crew that is capable of flying that aircraft at that time and in that place. The factors that must be respected when assigning a crew member line are called "Constraints" which include a number of federal regulations imposed by the FAA, as well as conform to any collective bargaining agreements. These include requirements for time flying, time between flights, total time flown in the month or week, and any leave, pay value, time credit, and training. Constraints imposed by the crew members' predetermined activities must also be respected.Crew scheduling methods
There are two general approaches to solving this complex crewing challenge; Bid Lines and PBS.Bid Lines
In the Bid Lines approach, pairings are placed within pre-built lines by Line Optimizer, a computer program that puts the pairings into "legal" lines, and does not take into account the individual crew members' preferences, nor the constraints imposed by crew members. The generic set of lines are then published for bidding. A crew member is free to choose any line and it will be awarded as long as no other senior crew member who also wants this same line. Unless the most senior in the bid package, crew member needs to submit multiple preferred lines in order to guarantee a preferred line; otherwise, a left over line will be awarded. By the bidding process, the preferred line may not be awarded completely, because the line was created without reference to specific crew member constraints, it may conflict with crew members' predetermined activities. The conflicting pairings must then be re-assigned to other crew members resulting in a wide range of inefficiencies. Clearly this post-award reallocation is costly to the airlines, and frustrating to crew members. These inefficiencies also force airlines to hire more crew members. However, bid line does offer a transparent and easy process to bid and to award, and in a lot cases the conflict itself actually benefits the crew members that being paid without the work according to the contracts. Though airlines management is eager to streamline operations and use their resources as best they can, crew members may still prefer the bid lines.PBS
In the PBS approach, the lines have not been created at the bidding, and the crew members have the ability to designate what kind of pairings, the properties of the line, and days off they prefer, thereby building a line themselves. PBS also allows crew members to bid reserve duties mixed with the pairings biddings. PBS provides a one-step process from the pairings to the lines that each crew member prefers and can legally cover.The real challenge for PBS is that it tries to solve two innately conflicted goals, honoring preferences without violating seniority and awarding all pairings.
Conventional PBS
In a conventional PBS, crew members make their bids and chooses their preferences based upon their own best interests. Once all the bids are made and the bid period ends, the program attempts to create the solution by an "optimization" process. Each crew member will be awarded the best line of his own definitions from available pairings at his seniority. For each crew member, when there are many best lines, the one with the least interest conflict to the junior crew members will be awarded, which is an advantage that interactive PBS cannot achieve. By the optimization, system finds a way to satisfy both senior and junior crew members while still honoring seniority and operation coverage requirement. The optimization process itself is complicated which may take many hours and multiple runs to achieve the optimal solution. A rejected preference happens when the pairing is awarded to senior, or overall coverage issue, or legality violation, and the reason for rejection will be provided.Interactive PBS
Dynamic and interactive PBS, in contrast, changes the process of bidding into a "continuous" process, where crew members can see the status of other crew member bids reflected as they bid. The web based presentation of this live and continuous schedule status is currently (as of 1-2010) a Patent Pending process of Mr. Christian Boegner. It is this live awareness which allows crew members to bid realistically because they see and can only bid for trips and days off that are available to them at their seniority. In the end the schedule which is solved is very efficient since crew members submit the preferences free of conflict with the other crew members, though not their best interests. It gives every crew member the "highest satisfaction". It is a relatively new approach. Currently (February 2011), there is only one company providing a dynamic real-time PBS application; Crewing Solutions based in California, founded by Christian Boegner.A somewhat similar interactive Preference Request System offered by Kernel Software is used by Lufthansa
Lufthansa
Deutsche Lufthansa AG is the flag carrier of Germany and the largest airline in Europe in terms of overall passengers carried. The name of the company is derived from Luft , and Hansa .The airline is the world's fourth-largest airline in terms of overall passengers carried, operating...
. It does not build complete schedules as does the Crewing Solutions PBS.
”Kernel Software strongly disagrees with this statement. It also thinks that Wikipedia is not the appropriate place for such discussions, and refers the interested reader of PBS to its web site for detailed information about this specific Crewing Solution PBS”.
Mr. Boegner is an expert in Heuristic algorithms. He is respected worldwide and regarded as the "Father of PBS" having introduced the concept in the 70's and eventually implemented in SmartPref, the Crewing Solutions product. There is competing school of thought that Linear Logic
Linear logic
Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...
is the best approach to solving the "problem" efficiently. The company SBS, he headed, installed over 100 scheduling systems with airlines. SBS was eventually sold to Boeing
Boeing
The Boeing Company is an American multinational aerospace and defense corporation, founded in 1916 by William E. Boeing in Seattle, Washington. Boeing has expanded over the years, merging with McDonnell Douglas in 1997. Boeing Corporate headquarters has been in Chicago, Illinois since 2001...
.
This dynamic real-time PBS uses heuristic algorithm running as a hosted Web application
Web application
A web application is an application that is accessed over a network such as the Internet or an intranet. The term may also mean a computer software application that is coded in a browser-supported language and reliant on a common web browser to render the application executable.Web applications are...
offers live current status of other crew members bids during the bidding process. A crew member designates their preferences, both globally and specifically, based on seeing real availability at that moment, at their seniority and submits a "Bid" for trips and work days. The PBS then assesses these new preferences and immediately builds a new schedule/solution, and presents this in the web based GUI
Gui
Gui or guee is a generic term to refer to grilled dishes in Korean cuisine. These most commonly have meat or fish as their primary ingredient, but may in some cases also comprise grilled vegetables or other vegetarian ingredients. The term derives from the verb, "gupda" in Korean, which literally...
to any viewing crew member. That solution combines a bidding crew member's preferences with the existing data to create the pairings and to generate the best quality crewing solution available at the time they bid. The PBS attempts to determine what is in the bidders best interest based on those preferences previously input and continues to consider all crew member preferences throughout the remaining bidding window.
As bidders continue to enter bids, the schedule begins to take shape. In the LIVE PBS environment a crew member can return to view the status of their choices at any time. They can elect to change their preferences and resubmit them if the environment has changed such that they now wish to try to improve their situation. During the bidding process, in order to have a realistic line, crew member has to constantly adjust his bids until all his senior crew members finalize their bids. Some crew members will come back later after bidding and see a less desirable line mainly due to overriding conflicts with the senior crew members. In these cases the bidding crew member must change his preferences until he bids what he CAN get and until he gets a line which is also compatible with the data at hand by compromising his interests.
The interactive PBS gives the problem of solving conflicted interests to crew members which leads to a much simpler design in system in comparison to a conventional PBS. The resulting bid is considered optimal in that the bid preference parameters are the most accurate and efficient with respect to constraints and preferences at the present state of the solution and the seniority of the crew member. However, at the beginning of the bid period even before choices or bids are made, a reliable initial base solution must be generated from the standby or default bids, of each crew member. Although at this initial stage, the results are far from real, in the end when every one submits their bids, the results will become realistic.
Without a LIVE PBS's interactive recalculation during the bid period, if crew members bid for certain pairings and/or days off heavily over others, at the end of the bid period either an advanced, time consuming algorithm needs to be implemented to solve the resultant conflicts automatically, or manual manipulation is used to fill the "open time" (unassigned pairings).
With the live interactive PBS, it only offers "left over" pairings to crew members and naturally forces the crew members to cover them with the advantage knowing of what their schedule will likely be.
Implement PBS
PBS is not a new concept and the products have been available in the market and used in many airlines for many years. The algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s used may be very different and usually lead to very different results and satisfactions. In addition, the user interfaces that provided for crew members to enter the preferences are also very different from vendor to vendor. The evaluation of the PBS products and the negotiation between the management and crew members are the most important and critical steps of a successful implementation of the PBS.