Bidline scheduling with equity by heuristic dynamic constraint aggregation

The bidline scheduling problem with equity arises in several North American airlines. It consists of determining anonymous monthly schedules, called bidlines, that will be subsequently assigned to the crew members according to their bids and seniority. These bidlines must satisfy safety and collective agreement rules. Furthermore, to ensure an equity between the employees, each bidline should have as much as possible the same number of days off and the same number of credited (paid) hours. In this paper, we propose an approximate set partitioning type formulation for this problem and two heuristics for solving it. The first one is a standard branch-and-price heuristic that relies on a rounding procedure to derive integer solutions. The second one is obtained by combining this first heuristic with a dynamic constraint aggregation method that was recently proposed in the literature. Computational results show that, for the largest tested instances, the dynamic constraint aggregation heuristic can produce better quality solutions in a fraction of the computational time required by the standard branch-and-p rice heuristic. (C) 2009 Elsevier Ltd. All rights reserved.