IDEAS home Printed from
   My bibliography  Save this article

Personnel Tour Scheduling When Starting-Time Restrictions Are Present


  • Michael J. Brusco

    (Information and Management Sciences Department, College of Business, The Florida State University, Tallahassee, Florida 32306-1042)

  • Larry W. Jacobs

    (Operations Management and Information Systems Department, Northern Illinois University, DeKalb, Illinois 60115)


This paper presents an effective solution strategy for an important category of personnel scheduling problems. Specifically, we address the restricted starting-time tour-scheduling problem (RSTP), which involves the determination of the hours of the day (shifts) and days of the week (days on) that employees are assigned to work. RSTP is characterized by restrictions on the number of daily time periods in which employees may begin their shifts. Moreover, the RSTP we consider contains constraints that require separation of starting times. Such restrictions are widely encountered in practice and are based on a number of factors including managerial concerns for control of employee movements, union contractual obligations, and employee preferences for common shift starting times. A two-stage heuristic solution strategy is proposed for RSTP. We developed eight heuristic procedures based on this strategy and applied them to four sets of labor requirements, for each of 27 United Airlines (UA) airport ground stations. One of the best of these procedures yielded solution costs that averaged only 1.36 full-time-equivalent employees above very conservative LP-based lower bounds. Moreover, the solution costs obtained using this procedure were, on average, 28 percent closer to the lower bounds than solution costs obtained using UA's current scheduling system. We conclude that the two-stage heuristic solution strategy is a valuable platform from which to develop procedures for generating near-optimal solutions to this difficult class of personnel scheduling problems.

Suggested Citation

  • Michael J. Brusco & Larry W. Jacobs, 1998. "Personnel Tour Scheduling When Starting-Time Restrictions Are Present," Management Science, INFORMS, vol. 44(4), pages 534-547, April.
  • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:4:p:534-547

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. R. N. Burns & M. W. Carter, 1985. "Work Force Size and Single Shift Schedules with Variable Demands," Management Science, INFORMS, vol. 31(5), pages 599-607, May.
    2. Fred F. Easton & Donald F. Rossin, 1991. "Sufficient Working Subsets for the Tour Scheduling Problem," Management Science, INFORMS, vol. 37(11), pages 1441-1451, November.
    3. Lauer, J & Jacobs, LW & Brusco, MJ & Bechtold, SE, 1994. "An interactive, optimization-based decision support system for scheduling part-time, computer lab attendants," Omega, Elsevier, vol. 22(6), pages 613-626, November.
    4. Ahmad I. Z. Jarrah & Jonathan F. Bard & Anura H. deSilva, 1994. "Solving Large-Scale Tour Scheduling Problems," Management Science, INFORMS, vol. 40(9), pages 1124-1144, September.
    5. John J. Bartholdi, III & H. Donald Ratliff, 1978. "Unnetworks, with Applications to Idle Time Scheduling," Management Science, INFORMS, vol. 24(8), pages 850-858, April.
    6. Bechtold, Stephen E. & Brusco, Michael J., 1994. "Working set generation methods for labor tour scheduling," European Journal of Operational Research, Elsevier, vol. 74(3), pages 540-551, May.
    7. James G. Morris & Michael J. Showalter, 1983. "Simple Approaches to Shift, Days-Off and Tour Scheduling Problems," Management Science, INFORMS, vol. 29(8), pages 942-950, August.
    8. Rudy Hung, 1994. "Multiple-Shift Workforce Scheduling Under the 3--4 Workweek with Different Weekday and Weekend Labor Requirements," Management Science, INFORMS, vol. 40(2), pages 280-284, February.
    9. Larry W. Jacobs & Michael J. Brusco, 1996. "Overlapping Start-Time Bands in Implicit Tour Scheduling," Management Science, INFORMS, vol. 42(9), pages 1247-1259, September.
    10. Gary M. Thompson, 1995. "Improved Implicit Optimal Modeling of the Labor Shift Scheduling Problem," Management Science, INFORMS, vol. 41(4), pages 595-607, April.
    11. Stephen E. Bechtold & Larry W. Jacobs, 1990. "Implicit Modeling of Flexible Break Assignments in Optimal Shift Scheduling," Management Science, INFORMS, vol. 36(11), pages 1339-1351, November.
    12. Brusco, Michael J. & Jacobs, Larry W., 1995. "Cost analysis of alternative formulations for personnel scheduling in continuously operating organizations," European Journal of Operational Research, Elsevier, vol. 86(2), pages 249-261, October.
    13. Kenneth R. Baker & Michael J. Magazine, 1977. "Workforce Scheduling with Cyclic Demands and Day-Off Constraints," Management Science, INFORMS, vol. 24(2), pages 161-167, October.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Giovanni Felici & Claudio Gentile, 2004. "A Polyhedral Approach for the Staff Rostering Problem," Management Science, INFORMS, pages 381-393.
    2. Robbins, Thomas R. & Harrison, Terry P., 2010. "A stochastic programming model for scheduling call centers with global Service Level Agreements," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1608-1619, December.
    3. Thompson, Gary M. & Pullman, Madeleine E., 2007. "Scheduling workforce relief breaks in advance versus in real-time," European Journal of Operational Research, Elsevier, vol. 181(1), pages 139-155, August.
    4. repec:pal:jorsoc:v:58:y:2007:i:8:d:10.1057_palgrave.jors.2602215 is not listed on IDEAS
    5. Rodolfo Cuevas & Juan-Carlos Ferrer & Mathias Klapp & Juan-Carlos Muñoz, 2016. "A mixed integer programming approach to multi-skilled workforce scheduling," Journal of Scheduling, Springer, vol. 19(1), pages 91-106, February.
    6. Thompson, Gary M. & Goodale, John C., 2006. "Variable employee productivity in workforce scheduling," European Journal of Operational Research, Elsevier, vol. 170(2), pages 376-390, April.
    7. Michael J. Brusco & Larry W. Jacobs, 2000. "Optimal Models for Meal-Break and Start-Time Flexibility in Continuous Tour Scheduling," Management Science, INFORMS, pages 1630-1641.
    8. Örmeci, E. Lerzan & Salman, F. Sibel & Yücel, Eda, 2014. "Staff rostering in call centers providing employee transportation," Omega, Elsevier, vol. 43(C), pages 41-53.
    9. Restrepo, María I. & Lozano, Leonardo & Medaglia, Andrés L., 2012. "Constrained network-based column generation for the multi-activity shift scheduling problem," International Journal of Production Economics, Elsevier, vol. 140(1), pages 466-472.
    10. Brusco, Michael J. & Jacobs, Larry W., 2001. "Starting-time decisions in labor tour scheduling: An experimental analysis and case study," European Journal of Operational Research, Elsevier, vol. 131(3), pages 459-475, June.
    11. Batta, Rajan & Berman, Oded & Wang, Qian, 2007. "Balancing staffing and switching costs in a service center with flexible servers," European Journal of Operational Research, Elsevier, vol. 177(2), pages 924-938, March.


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:44:y:1998:i:4:p:534-547. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.