Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets

James B. Orlin
Additional contact information
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1982, vol. 30, issue 4, 760-776

Abstract: In this paper we consider countably infinite partially ordered sets (posets) in which the order relations occur periodically. We show that the problem of determining the minimum number of chains (completely ordered subsets) needed to cover all of the elements may be solved efficiently as a finite network flow problem. A special case of the chain-cover problem for periodic posets is the problem of minimizing the number of individuals to meet a fixed periodically repeating set of tasks with set-up times between tasks. For example, if we interpret tasks as flights and individuals as airplanes, the resulting problem is to minimize the number of airplanes needed to fly a fixed daily repeating schedule of flights, where deadheading between airports is allowed.

Keywords: 432 an application of periodic posets; 484 periodic vehicle scheduling via network flows; 832 the minimum number of vehicles to meet a periodic schedule (search for similar items in EconPapers)
Date: 1982
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.30.4.760 (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:oropre:v:30:y:1982:i:4:p:760-776

Access Statistics for this article

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