Groupe d’études et de recherche en analyse des décisions


An Exact Solution Approach for the PBS Problem

, , et

This paper introduces the first exact approach for constructing aircrew member personalized monthly work schedules when a preferential bidding system (PBS) is used. With such a system, each employee bids for their preferred activities, yielding a bidding score for each feasible schedule. The PBS problem thus consists of assigning to each employee a schedule that maximizes, in order of seniority, its preferences while covering all crew pairings. The proposed exact solution approach relies on column generation and, when a tentative maximum score for a crew member is established, it explicitly enumerates for that employee all feasible schedules with that score. Tests on real-life cases show that this approach can substantially improve the quality of the solutions produced by the best known existing method (Gamache et al., 1998b) in similar solution times.

, 22 pages