IDEAS home Printed from
   My bibliography  Save this article

Sufficient Working Subsets for the Tour Scheduling Problem


  • Fred F. Easton

    (School of Management, Syracuse University, Syracuse, New York 13244-2130)

  • Donald F. Rossin

    (Owen Graduate School of Management, Vanderbilt University, Nashville, Tennessee 37203)


Mathematical programs to schedule service employees at minimum cost represent each feasible schedule, or tour, with an integer variable. In some service organizations, policies governing employee scheduling practices may permit millions of different tours. A common heuristic strategy is to reformulate the problem from a small working subset of the feasible tours. Solution quality depends on the number and types of schedules included in the model. This paper describes a working subset heuristic based on column generation. The method is general and can accommodate a mix of full- and part-time employees. Experiments revealed its formulations had objective values indistinguishable from those of models using all feasible tours, and significantly lower than those generated by alternative working subset procedures.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:ormnsc:v:37:y:1991:i:11:p:1441-1451

    Download full text from publisher

    File URL:
    Download Restriction: no


    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, vol. 50(3), pages 381-393, March.
    2. 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.
    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. Gerard M. Campbell, 1999. "Cross-Utilization of Workers Whose Capabilities Differ," Management Science, INFORMS, vol. 45(5), pages 722-732, May.
    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. Easton, F. F. & Rossin, D. F., 1997. "Overtime schedules for full-time service workers," Omega, Elsevier, vol. 25(3), pages 285-299, June.
    8. 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.
    9. 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.
    10. 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.
    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. Brusco, Michael J., 2015. "A bicriterion algorithm for the allocation of cross-trained workers based on operational and human resource objectives," European Journal of Operational Research, Elsevier, vol. 247(1), pages 46-59.
    13. 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.
    14. 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.
    15. 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.
    16. 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:37:y:1991:i:11:p:1441-1451. 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.

    We have no 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.

    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.