A Dynamic Programming Approach to Sequencing Problems

DOI10.1137/0110015zbMath0106.14103OpenAlexW1969186119WikidataQ55899758 ScholiaQ55899758MaRDI QIDQ3292045

Michael Held, Richard M. Karp

Publication date: 1962

Published in: Journal of the Society for Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0110015

zbMATH Keywords

applications of probability theory, mathematical programming

Related Items (only showing first 100 items - show all)

A compact labelling scheme for series-parallel graphs ⋮ A dynamic programming method for single machine scheduling ⋮ Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine ⋮ Greedy can beat pure dynamic programming ⋮ Job shop scheduling with setup times, deadlines and precedence constraints ⋮ Polynomial time algorithms for some minimum latency problems ⋮ Robust combinatorial optimization with variable cost uncertainty ⋮ Tabu search performance on the symmetric travelling salesman problem ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ An algorithm for finding Hamilton paths and cycles in random graphs ⋮ Cyclic inventory routing in a line-shaped network ⋮ The bi-objective mixed capacitated general routing problem with different route balance criteria ⋮ Single machine scheduling under market uncertainty ⋮ Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties ⋮ A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem ⋮ The dynamic programming method in the generalized traveling salesman problem ⋮ Solving large batches of traveling salesman problems with parallel and distributed computing ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective ⋮ Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ GIS technology as an environment for testing an advanced mathematical model for optimization of road maintenance ⋮ Distance conserving reductions for nonoriented networks ⋮ Customer order scheduling on a single machine with family setup times: complexity and algorithms ⋮ Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem ⋮ Correlated topographic analysis: estimating an ordering of correlated components ⋮ Submodularity and the traveling salesman problem ⋮ Minimizing total earliness and tardiness on a single machine using a hybrid heuristic ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Parameterized complexity of superstring problems ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ Kernel bounds for path and cycle problems ⋮ Exponential approximation schemata for some network design problems ⋮ Exact algorithms for inventory constrained scheduling on a single machine ⋮ The traveling purchaser problem with stochastic prices: exact and approximate algorithms ⋮ Evaluation of permanents in rings and semirings ⋮ Multi-product lot-sizing and sequencing on a single imperfect machine ⋮ A multi-commodity, capacitated pickup and delivery problem: the single and two-vehicle cases ⋮ Dominance rules in combinatorial optimization problems ⋮ On the choice of step size in subgradient optimization ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ A survey of scheduling methods for multiprocessor systems ⋮ The development of genetic algorithms for the finite capacity scheduling of complex products, with multiple levels of product structure. ⋮ Scheduling with time-dependent discrepancy times ⋮ Finding and enumerating Hamilton cycles in 4-regular graphs ⋮ A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem ⋮ Probabilistic analysis of solving the assignment problem for the traveling salesman problem ⋮ A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation ⋮ Dynamic programming approach to the single-machine sequencing problem with different due-dates ⋮ Hybrid algorithm for sequencing with bicriteria ⋮ Single facility multi-class job scheduling ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ Dynamic programming meets the principle of inclusion and exclusion ⋮ An exact iterative search algorithm for constrained Markov decision processes ⋮ On the complexity of dynamic programming for sequencing problems with precedence constraints ⋮ Evolutionary algorithms and dynamic programming ⋮ Elements of dynamic programming in extremal routing problems ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees ⋮ On cutwidth parameterized by vertex cover ⋮ Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis ⋮ FMS scheduling based on timed Petri net model and reactive graph search ⋮ Finding supported paths in heterogeneous networks ⋮ A note on the effect of neighborhood structure in simulated annealing ⋮ Computing tree-depth faster than \(2^n\) ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Approximation schemes for the generalized traveling salesman problem ⋮ Routing under constraints: problem of visit to megalopolises ⋮ Exploiting planarity in separation routines for the symmetric traveling salesman problem ⋮ Optimal partitions for shop floor control in semiconductor wafer fabrication ⋮ Limitations of incremental dynamic programming ⋮ Single machine scheduling with flow time and earliness penalties ⋮ Algorithm engineering for color-coding with applications to signaling pathway detection ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Inclusion and exclusion algorithm for the Hamiltonian path problem ⋮ Design tools for reporter strands and DNA origami scaffold strands ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ Reduced complexity dynamic programming based on policy iteration ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ On estimating the number of order ideals in partial orders, with some applications ⋮ Constrained optimal routing ⋮ Finding paths of length \(k\) in \(O^{*}(2^k)\) time ⋮ Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient ⋮ A diagonal completion and 2-optimal procedure for the travelling salesman problem ⋮ Four solution techniques for a general one machine scheduling problem. A comparative study ⋮ A dynamic programming formulation for the one machine sequencing problem ⋮ The Euclidean traveling salesman problem is NP-complete ⋮ Designing group behavior algorithms for autonomous underwater vehicles in the underwater local heterogeneities survey problem ⋮ A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem ⋮ The use of dynamic programming in genetic algorithms for permutation problems ⋮ Nondeterministic graph searching: from pathwidth to treewidth ⋮ Sevast'yanov's algorithm for the flow-shop scheduling problem ⋮ MIP modelling of changeovers in production planning and scheduling problems ⋮ An exact algorithm for subgraph homeomorphism ⋮ Sorting can exponentially speed up pure dynamic programming ⋮ Job selection and sequencing on a single machine in a random environment ⋮ Partitioning heuristics for two geometric maximization problems ⋮ Special cases of the traveling salesman problem ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ Exact algorithms for intervalizing coloured graphs ⋮ A cutting plane procedure for the travelling salesman problem on road networks

This page was built for publication: A Dynamic Programming Approach to Sequencing Problems