Solving Large-Scale Tour Scheduling Problems

Ahmad I. Z. Jarrah, Jonathan F. Bard and Anura H. deSilva
Additional contact information
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

Management Science, 1994, vol. 40, issue 9, 1124-1144

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.

Keywords: shift scheduling; days-off scheduling; tour scheduling; integer programming; branch and bound; U.S. postal service (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.40.9.1124 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:40:y:1994:i:9:p:1124-1144

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().