Open Access. Powered by Scholars. Published by Universities.®
- File Type
Articles 1 - 4 of 4
Full-Text Articles in Industrial Organization
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.
Testing Heuristics: We Have It All Wrong, John Hooker
Testing Heuristics: We Have It All Wrong, John Hooker
John Hooker
The competitive nature of most algorithmic experimentation is a source of problems that are all too familiar to the research community. It is hard to make fair comparisons between algorithms and to assemble realistic test problems. Competitive testing tells us which algorithm is faster but not why. Because it requires polished code, it consumes time and energy that could be better spent doing more experiments. This article argues that a more scientific approach of controlled experimentation, similar to that used in other empirical sciences, avoids or alleviates these problems. We have confused research and development; competitive testing is suited only …
Optimal Movement Of Factory Cranes, Ionuţ Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, John Hooker
Optimal Movement Of Factory Cranes, Ionuţ Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, John Hooker
John Hooker
We study the problem of finding optimal space-time trajectories for two factory cranes or hoists that move along a single overhead track. Each crane is a assigned a sequence of pickups and deliveries at specified locations that must be performed within given time windows. The cranes must be operated so as not to interfere with each other, although one crane may need to yield to another. The objective is generally to follow a production schedule as closely as possible. We show that only certain types of trajectories need be considered to obtain an optimal solution. This simplifies the operation of …
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 …