2001 | OriginalPaper | Buchkapitel
Days-off Scheduling in Public Transport Companies
verfasst von : Dulce Pedrosa, Miguel Constantino
Erschienen in: Computer-Aided Scheduling of Public Transport
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The assignment of weekly rests to workers in large companies is, in general, conditioned by strict labor union rules. Some of these rules establish, e.g., the (average) number of rest days per week, a minimum and a maximum number of days for the length of a rest period or work period, the number of weekends or Sundays off each p weeks, etc. On the other hand, companies must have enough workers available each day, in order to satisfy the internal workforce demand. The solution approach adopted by some companies consists of assigning workers to cyclic schedules. All workers assigned to the same cyclic schedule have the same type of rest/work periods. Since the weekly workforce demand is not constant in general, these cyclic schedules have to be carefully planned in order to minimize the necessary resources (number of workers).We propose an integer programming model for which the solutions consist of a set of cyclic schedules as well as the number of workers assigned to each schedule. Since the number of possible schedules may be very large, we use column generation to solve the linear programming (LP) relaxation, and to obtain a set of basic cyclic schedules. The number of workers assigned to each schedule is then obtained by using a simple LP heuristic. To solve the pricing subproblem within the column generation procedure we use a network in which paths correspond to schedules, and solve a shortest path problem. This algorithm has been integrated in the GIST Decision Support System, in use by several public transport companies in Portugal. We also present our computational experience with some large randomly generated instances.