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

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.