IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v40y1994i9p1124-1144.html
   My bibliography  Save this article

Solving Large-Scale Tour Scheduling Problems

Author

Listed:
  • Ahmad I. Z. Jarrah

    (American Airlines Decision Technologies, P.O. Box 619616, Dallas-Fort Worth Airport, Texas 75261-9616)

  • Jonathan F. Bard

    (Graduate Program in Operations Research and Industrial Engineering, Department of Mechanical Engineering, University of Texas, Austin, Texas 78712-1063)

  • Anura H. deSilva

    (Planmatics, Inc., 6315 Poe Road, Bethesda, Maryland 20817)

Abstract

For a given planning horizon, workforce composition and set of labor requirements, personnel scheduling often reduces to solving three problems. The first is concerned with the assignment of days off; the second involves assigning workers to shifts during the day; and the third involves the construction of weekly tours. In many manufacturing facilities, tour scheduling is easy because the start and end times of shifts are invariant, and no work takes place on the weekend. But when daily patterns vary, such as in the airlines, processing, and public service industries, and when part-timers make up a portion of the workforce, the complexity of the overall problem increases dramatically. This paper presents a new methodology for solving the combined shift and days-off scheduling problem when the labor requirements span less than 24 hours per day. We begin with an integer programming formulation and then introduce a set of aggregate variables and related cuts. When the aggregate variables are fixed the original problem decomposes into seven subproblems (one for each day of the week) that are much easier to solve. A partial enumeration scheme and a heuristic for ensuring feasibility are employed to find upper and lower bounds which converge rapidly to near-optima. The methodology is applied to tour scheduling at general mail facilities (GMFs). These facilities are located in most urban areas and process millions of mail pieces daily for local and regional distribution. The model accounts for the principal constraints in the U.S. Postal Service labor contract, including half-hour breaks, minimum full-time to part-time ratios, and variable start times. Also considered are four and five day work weeks, and the possibility of assigning workers across labor categories. A full analysis of the Providence, Rhode Island facility is presented.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormnsc:v:40:y:1994:i:9:p:1124-1144
    DOI: 10.1287/mnsc.40.9.1124
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.40.9.1124
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.40.9.1124?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. Brusco, Michael J. & Johns, Tony R., 1996. "A sequential integer programming method for discontinuous labor tour scheduling," European Journal of Operational Research, Elsevier, vol. 95(3), pages 537-548, December.
    2. Hua Ni & Hernán Abeledo, 2007. "A branch-and-price approach for large-scale employee tour scheduling problems," Annals of Operations Research, Springer, vol. 155(1), pages 167-176, November.
    3. Gerard M. Campbell, 1999. "Cross-Utilization of Workers Whose Capabilities Differ," Management Science, INFORMS, vol. 45(5), pages 722-732, May.
    4. Idris Addou & François Soumis, 2007. "Bechtold-Jacobs generalized model for shift scheduling with extraordinary overlap," Annals of Operations Research, Springer, vol. 155(1), pages 177-205, November.
    5. Michael J. Brusco & Larry W. Jacobs, 2000. "Optimal Models for Meal-Break and Start-Time Flexibility in Continuous Tour Scheduling," Management Science, INFORMS, vol. 46(12), pages 1630-1641, December.
    6. Haase, Knut, 1999. "Retail business staff scheduling under complex labor relations," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 511, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Mark W. Isken & Osman T. Aydas, 2022. "A tactical multi-week implicit tour scheduling model with applications in healthcare," Health Care Management Science, Springer, vol. 25(4), pages 551-573, December.
    8. Eveborn, Patrik & Flisberg, Patrik & Ronnqvist, Mikael, 2006. "Laps Care--an operational system for staff planning of home care," European Journal of Operational Research, Elsevier, vol. 171(3), pages 962-976, June.
    9. Jonathan F. Bard & Lin Wan, 2008. "Workforce Design with Movement Restrictions Between Workstation Groups," Manufacturing & Service Operations Management, INFORMS, vol. 10(1), pages 24-42, November.
    10. Jonathan Bard & David Morton & Yong Wang, 2007. "Workforce planning at USPS mail processing and distribution centers using stochastic optimization," Annals of Operations Research, Springer, vol. 155(1), pages 51-78, November.
    11. 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.
    12. Lagodimos, A. G. & Leopoulos, V., 2000. "Greedy heuristic algorithms for manpower shift planning," International Journal of Production Economics, Elsevier, vol. 68(1), pages 95-106, October.
    13. Aykin, Turgut, 2000. "A comparative evaluation of modeling approaches to the labor shift scheduling problem," European Journal of Operational Research, Elsevier, vol. 125(2), pages 381-397, September.
    14. X Zhang & A Chakravarthy & Q Gu, 2009. "Equipment scheduling problem under disruptions in mail processing and distribution centres," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(5), pages 598-610, May.
    15. Karen Puttkammer & Rainer Kleber & Tobias Schulz & Karl Inderfurth, 2011. "Simultane Maschinenbelegungs- und Personaleinsatzplanung in KMUs anhand eines Fallbeispiels aus der Druckereibranche," FEMM Working Papers 110010, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    16. L Wan & J F Bard, 2007. "Weekly staff scheduling with workstation group restrictions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(8), pages 1030-1046, August.
    17. Easton, F. F. & Rossin, D. F., 1997. "Overtime schedules for full-time service workers," Omega, Elsevier, vol. 25(3), pages 285-299, June.
    18. Cai, X. & Li, K. N., 2000. "A genetic algorithm for scheduling staff of mixed skills under multi-criteria," European Journal of Operational Research, Elsevier, vol. 125(2), pages 359-369, September.
    19. Easton, Fred F. & Mansour, Nashat, 1999. "A distributed genetic algorithm for deterministic and stochastic labor scheduling problems," European Journal of Operational Research, Elsevier, vol. 118(3), pages 505-523, November.
    20. María I. Restrepo & Bernard Gendron & Louis-Martin Rousseau, 2016. "Branch-and-Price for Personalized Multiactivity Tour Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 334-350, May.
    21. Hur, Daesik & Mabert, Vincent A. & Bretthauer, K.M.Kurt M., 2004. "Real-time schedule adjustment decisions: a case study," Omega, Elsevier, vol. 32(5), pages 333-344, October.

    Corrections

    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:40:y:1994:i:9:p:1124-1144. See general information about how to correct material in RePEc.

    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.

    We have no bibliographic references for this item. You can help adding them by using 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.