Operations Research · 2013 · 77 citations · 13 references
ComputingComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingCombinatorial OptimizationConstraint SatisfactionConstraint-based SchedulingJob SequencingScheduling TheoryConstraintsRouting ProblemsScheduling ConstraintsScheduling Problems
Sequencing problems are among the most prominent problems studied in operations research, with primary application in, e.g., scheduling and routing. We propose a novel approach to solving generic sequencing problems using multivalued decision diagrams (MDDs). Because an MDD representation may grow exponentially large, we apply MDDs of limited size as a discrete relaxation to the problem. We show that MDDs can be used to represent a wide range of sequencing problems with various side constraints and objective functions, and we demonstrate how MDDs can be added to existing constraint-based scheduling systems. Our computational results indicate that the additional inference obtained by our MDDs can speed up a state-of-the art solver by several orders of magnitude, for a range of different problem classes.
13
Scheduling: Theory, Algorithms, and Systems
Michael Pinedo · IIE Transactions · 1996 · 6.3K citations
An Optimal Algorithm for the Traveling Salesman Problem with Time Windows
Yvan Dumas, Jacques Desrosiers, Éric Gélinas et al. · Operations Research · 1995 · 340 citations