Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Entire DC Network
A Generalized Dilworth's Theorem, With Application To Routing And Scheduling, John N. Hooker, N R. Natraj
A Generalized Dilworth's Theorem, With Application To Routing And Scheduling, John N. Hooker, N R. Natraj
John Hooker
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.
Inference Duality As A Basis For Sensitivity Analysis, John N. Hooker
Inference Duality As A Basis For Sensitivity Analysis, John N. Hooker
John Hooker
The constraint programming community has recently begun to address certain types of optimization problems. These problems tend to be discrete or to have discrete elements. Although sensitivity analysis is well developed for continuous problems, progress in this area for discrete problems has been limited. This paper proposes a general approach to sensitivity analysis that applies to both continuous and discrete problems. In the continuous case, particularly in linear programming, sensitivity analysis can be obtained by solving a dual problem. One way to broaden this result is to generalize the classical idea of a dual to that of an ldquoinference dual,rdquo …
Factory Crane Scheduling By Dynamic Programming, Ionuţ D. Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, John N. Hooker
Factory Crane Scheduling By Dynamic Programming, Ionuţ D. Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, John N. Hooker
John Hooker
We describe a specialized dynamic programming algorithm for factory crane scheduling. An innovative data structure controls the memory requirements of the state space and enables solution of problems of realistic size. The algorithm finds optimal spacetime trajectories for two factory cranes or hoists that move along a single overhead track. Each crane is assigned a sequence of pickups and deliveries at specified locations that must be performed within given time windows. The cranes must not interfere with each other, although one may yield to the other. The state space representation permits a wide variety of constraints and objective functions. It …