A Generalized Dilworth's Theorem, with Application to Routing and Scheduling

Dilworth's theorem states a duality relation between minimum chain decompositions of a directed, acyclic graph and maximum antichains. We generalize the theorem to apply when the chains of the decomposition are required to contain the chains of an initial decomposition. We show that duality obtains precisely when an associated undirected graph is perfect. We apply this result to a vehicle routing and scheduling problem with time windows. Here each chain of the initial decomposition contains nodes that correspond to the pickup, delivery and possibly intermediate stops associated with a piece of cargo.