×

Generating, scheduling and rostering of shift crew-duties: applications at the Hong Kong international airport. (English) Zbl 1102.90362

Summary: In the context of manpower planning, goal programming (GP) is extremely useful for generating shift duties of fixed length. A fixed-length duty consists of a fixed number of contiguous hours of work in a day, with a meal/rest break somewhere preferably around the middle of these working hours. It is such properties that enable the straightforward, yet flexible GP modeling. We propose GP models for an integrated problem of crew duties assignment, for baggage services section staff at the Hong Kong International Airport. The problem is solved via decomposition into its duties generating phase – a GP planner, followed by its GP scheduling and rostering phase. The results can be adopted as a good crew schedule in the sense that it is both feasible, satisfying various work conditions, and “optimal” in minimizing idle shifts.

MSC:

90B70 Theory of organizations, manpower planning in operations research
90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

LINDO; LINGO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Azmat, C. S.; Widmer, M., A case study of single shift planning and scheduling under annualized hours: A simple three-step approach, European Journal of Operational Research, 153, 148-175 (2004) · Zbl 1053.90032
[2] Baker, K., Workforce allocation in cyclical scheduling problems: A survey, Operational Research Quarterly, 27, 155-167 (1976)
[3] Balakrishnan, N.; Wong, R. T., A network model for the rotating workforce scheduling problem, Networks, 20, 25-42 (1990)
[4] Ball, M.; Bodin, L.; Dial, R., A matching based heuristics for scheduling mass transit crews and vehicles, Transportation Science, 17, 4-31 (1983)
[5] Bartholdi, J.; Ratliff, H., Unnetworks, with applications to idle time scheduling, Management Science, 4, 850-858 (1978) · Zbl 0383.90053
[6] Bellanti, F.; Carello, G.; Della Croce, F.; Tadei, R., A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153, 28-40 (2004) · Zbl 1053.90090
[7] Bodin, L.; Golden, B.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews: The state of the art, Computer & Operations Research, 10, 63-211 (1983)
[8] Brusco, M. J.; Jacobs, L. W., Optimal models for meal-break and start-time flexibility in continuous tour scheduling, Management Science, 46, 1630-1641 (2000) · Zbl 1232.90204
[9] Burke, E.; Petrovic, S., Timetabling and rostering, European Journal of Operational Research, 153, 1-2 (2004)
[10] Caprara, A.; Fischetti, M.; Vigo, D.; Toth, P., Modeling and solving the crew rostering problem, Operations Research, 46, 820-830 (1998) · Zbl 0987.90035
[11] Caprara, A.; Fischetti, M.; Toth, P., A heuristic method for the set covering problem, Operations Research, 47, 730-743 (1999) · Zbl 0976.90086
[12] Caprara, A.; Monaci, M.; Toth, P., Models and algorithms for a staff scheduling problem, Mathematical Programming, 98, 445-476 (2003) · Zbl 1160.90471
[13] Carpaneto, G.; Toth, P., Primal-dual algorithms for the assignment problem, Discrete Applied Mathematics, 18, 137-153 (1987) · Zbl 0632.90041
[14] Carraresi, P.; Gallo, G., Network models for vehicle and crew scheduling, European Journal of Operational Research, 16, 139-151 (1984) · Zbl 0537.90053
[15] Chu, S. C.K., A goal programming model for crew duties generation, Journal of Multi-criteria Decision Analysis, 10, 143-151 (2001) · Zbl 1015.90038
[16] Chu, S. C.K.; Chan, E. C.H., Crew scheduling of light rail transit in Hong Kong: From modeling to implementation, Computers & Operations Research, 25, 887-894 (1998) · Zbl 1042.90561
[17] Chu, S. C.K.; So, M. M.C., Generation of fixed-length duties by GP formulation, International Journal of Applied Mathematics, 13, 9-21 (2003) · Zbl 1070.90052
[18] Chu, S. C.K.; Yuen, C. S.Y., Planning and scheduling staff duties by goal programming, (Tanino, T.; Tanaka, T.; Inuiguchi, M., Multi-Objective Programming and Goal-Programming, Advances in Soft Computing (2003), Springer-Verlag), 309-316 · Zbl 1116.90346
[19] Desrochers, M.; Soumis, F., A column generation approach to the urban transit crew scheduling problem, Transportation Science, 23, 1-13 (1989) · Zbl 0668.90043
[20] Desrochers, M.; Gilbert, J.; Sauve, M.; Soumis, F., CREW-OPT: Sub-problem modeling in a column generation approach to the urban transit crew scheduling problem, (Desrochers, M.; Rousseau, J. M., Computer-Aided Transit Scheduling. Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 386 (1992), Springer-Verlag), 395-406
[21] Dimopoulou, M.; Miliotis, P., An automated university course timetabling system developed in a distributed environment: A case study, European Journal of Operational Research, 153, 136-147 (2004) · Zbl 1053.90019
[22] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 3-27 (2004) · Zbl 1053.90034
[23] Falkner, J. C.; Ryan, D. M., Aspects of bus crew scheduling using a set partitioning model, (Computer-Aided Transit Scheduling: Proceedings of the Fourth Conference (1987), Springer-Verlag), 91-103
[24] Falkner, J. C.; Ryan, D. M., EXPRESS: Set partitioning for bus crew scheduling in Christchurch, (Desrochers, M.; Rousseau, J. M., Computer-Aided Transit Scheduling. Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 386 (1992), Springer-Verlag), 359-378
[25] Gamache, M.; Soumis, F., A method for optimally solving the rostering problem, (Gang, Y., Operations Research in the Airline Industry (1998), Kluwer Publishing Company: Kluwer Publishing Company Norwell, Massachusetts), 124-157
[26] Gamache, M., Soumis, F., Marquis, G., Desrosiers, J., 1994. A column generation approach for large scale aircrew rostering problems. Les Cahiers du GERAD, G-94-20, Montréal.; Gamache, M., Soumis, F., Marquis, G., Desrosiers, J., 1994. A column generation approach for large scale aircrew rostering problems. Les Cahiers du GERAD, G-94-20, Montréal. · Zbl 1041.90513
[27] Hagberg, B., An assignment approach to the rostering problem, (Rousseau, J. M., Computer Scheduling of Public Transport, vol. 2 (1985), North-Holland)
[28] Lessard, R.; Rousseau, J. M.; Dupuis, D., HASTUS I: A mathematical programming approach to the bus driver scheduling problem, (Wren, A., Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (1981), North-Holland), 255-268
[29] Mason, A. J.; Ryan, D. M.; Panton, D. M., Integrated simulation, heuristic and optimization approaches to staff scheduling, Operations Research, 46, 161-175 (1998) · Zbl 0987.90525
[30] Musliu, N.; Schaerf, A.; Slany, W., Local search for shift design, European Journal of Operational Research, 153, 51-64 (2004) · Zbl 1053.90043
[31] Patrikalakis, I.; Xerocostas, D., A new decomposition scheme of the urban public transit scheduling problem, (Desrochers, M.; Rousseau, J. M., Computer-Aided Transit Scheduling. Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 386 (1992), Springer-Verlag), 407-425
[32] Ryan, D. M.; Falkner, J. C., On the integer properties of scheduling set partitioning models, European Journal of Operational Research, 35, 442-456 (1987) · Zbl 0639.90072
[33] Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, (Wren, A., Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (1981), North-Holland), 269-280 · Zbl 0327.90030
[34] Schönberger, J.; Mattfed, D. C.; Kopfer, H., Memetic Algorithm timtabling for non-commercial sport leagues, European Journal of Operational Research, 153, 102-116 (2004) · Zbl 1137.90517
[35] Schrage, L., 1999. Optimization Modeling with LINGO, 3/e. Lindo Systems Inc.; Schrage, L., 1999. Optimization Modeling with LINGO, 3/e. Lindo Systems Inc.
[36] Segal, M., The operator-scheduling problem: A network flow approach, Operations Research, 22, 808-823 (1974) · Zbl 0283.90024
[37] Valouxis, C.; Housos, E., Combined bus and driver scheduling, Computers & Operations Research, 29, 243-259 (2002) · Zbl 0993.90054
[38] Vance, P. H.; Barnhart, C.; Johnson, E. L.; Nemhauser, G. L., Airline crew scheduling: A new formulation and decomposition algorithm, Operations Research, 45, 188-200 (1997) · Zbl 0891.90087
[39] Wren, A.; Smith, B. M.; Miller, A. J., Complementary approaches to crew scheduling, (Rousseau, J. M., Computer Scheduling of Public Transport, vol. 2 (1985), North-Holland), 263-278
[40] Yuen, C.S.Y., 2000. Crew scheduling and rostering for airport baggage services: An optimization approach. M.Phil Thesis, University of Hong Kong. Hong Kong, 174pp.; Yuen, C.S.Y., 2000. Crew scheduling and rostering for airport baggage services: An optimization approach. M.Phil Thesis, University of Hong Kong. Hong Kong, 174pp.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.