A Dynamic Programming Approach to Sequencing Problems
From MaRDI portal
Publication:3292045
DOI10.1137/0110015zbMath0106.14103OpenAlexW1969186119WikidataQ55899758 ScholiaQ55899758MaRDI QIDQ3292045
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
Related Items
On sequential traversal of sets, Sparktope: linear programs from algorithms, A 3/2-Approximation for the Metric Many-Visits Path TSP, Unnamed Item, One task of routing jobs in high radiation conditions, Sequential algorithm for the solution of problems of combinatorial optimization on permutations, Some constrained shortest-route problems, The traveling-salesman problem and minimum spanning trees: Part II, A general framework for enumerating equivalence classes of solutions, Using an \(A^\ast\)-based framework for decomposing combinatorial optimization problems to employ NISQ computers, In-line kitting for part feeding of assembly lines: workload balancing and storage assignment to reduce the workers' walking effort, Sign depth tests in multiple regression, Two-stage dynamic programming in the routing problem with decomposition, Exact Algorithms for Edge Domination, Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems, Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition, Energy minimizing order picker forklift routing problem, A 3/4 differential approximation algorithm for traveling salesman problem, Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm, On Submodular Search and Machine Scheduling, Minimax routing problem with a system of priority tasks, Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals, On the Application of the Minimax Traveling Salesman Problem in Aviation Logistics, A bi-criteria moving-target travelling salesman problem under uncertainty, A bottleneck routing problem with a system of priority tasks, A note on a single-shift days-off scheduling problem with sequence-dependent labor costs, The single robot line coverage problem: Theory, algorithms, and experiments, Optimizing multi-inserts in routing problems with constraints, On the question of the optimization of permutations in the problem with dynamic constraints, Time complexity of the analyst's traveling salesman algorithm, Finding a Hamilton cycle fast on average using rotations and extensions, OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS, Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems, On one routing task with the optimization of the start-finish point, The routing problems with optimization of the starting point: dynamic programming, When polynomial approximation meets exact computation, Special Frequency Quadrilaterals and an Application, An Active Global Attack Model for Sensor Source Location Privacy: Analysis and Countermeasures, A geometrical method in combinatorial complexity, To the question of optimization of the starting point in the routing problem with restrictions, The travelling salesman and the PQ-tree, When polynomial approximation meets exact computation, Integer programming approaches to the travelling salesman problem, Sequencing jobs on a single machine: A neural network approach, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Dynamic programming method in the generalized traveling salesman problem: the influence of inexact calculations., A dual algorithm for the one-machine scheduling problem, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Production scheduling of independent jobs on parallel identical processors, Unnamed Item, Unnamed Item, Some optimal path problems subject to improvements, Unnamed Item, Solving a Routing Problem with the Aid of an Independent Computations Scheme, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Disjoint paths and connected subgraphs for \(H\)-free graphs, Using cutting planes to solve the symmetric Travelling Salesman problem, Disjoint paths and connected subgraphs for \(H\)-free graphs, On one routing problem modeling movement in radiation fields, Unnamed Item, Оptimization of the Start Point in the Gtsp with the Precedence Conditions, Fast exact algorithms for survivable network design with uniform requirements, Lot-Sizing and Sequencing on a Single Imperfect Machine, Approximation Limitations of Pure Dynamic Programming, Select and permute: an improved online framework for scheduling to minimize weighted completion time, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth, ON ROUTING PROBLEM WITH STARTING POINT OPTIMIZATION, Improving TSP Tours Using Dynamic Programming over Tree Decompositions., Computing treewidth on the GPU, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem, Unnamed Item, On the refinement of bounds of heuristic algorithms for the traveling salesman problem, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding, Validation of subgradient optimization, A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation, 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, Gantry crane and shuttle car scheduling in modern rail-rail transshipment yards, An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization, The searching over separators strategy to solve some NP-hard problems in subexponential time, On Cutwidth Parameterized by Vertex Cover, Further results on the probabilistic traveling salesman problem, Embedded local search approaches for routing optimization, On the Fine-Grained Complexity of Rainbow Coloring, From symmetry to asymmetry: generalizing TSP approximations by parametrization, Disentangling relationships in symptom networks using matrix permutation methods, The probabilistic travelling salesman problem with crowdsourcing, Good triangulations yield good tours, Solving the max-cut problem using eigenvalues, Minimizing flowtime and missed due-dates in single-machine sequencing, Minimizing the sum of weighted completion times with unrestricted weights, A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights, Treewidth computation and extremal combinatorics, Method of scaling in approximate solution of the traveling salesman problem, An exact algorithm with linear complexity for a problem of visiting megalopolises, Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension, The simultaneous semi-random model for TSP, A mathematical model for supply chain management of blood banks in India, Deep policy dynamic programming for vehicle routing problems, On the analysis of optimization problems in arc-dependent networks, Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions, Vehicle routing on road networks: how good is Euclidean approximation?, Reinforcement learning for combinatorial optimization: a survey, Edge Elimination in TSP Instances, Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems, Parameterized edge Hamiltonicity, End-Vertices of Graph Search Algorithms, On the complexity landscape of connected \(f\)-factor problems, Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries, Incremental versus non-incremental dynamic programming, Empirical working time distribution-based line balancing with integrated simulated annealing and dynamic programming, Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation, Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals, A new graph model and algorithms for consistent superstring problems , Solving the single crane scheduling problem at rail transshipment yards, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Exact algorithms for finding longest cycles in claw-free graphs, Sharp separation and applications to exact and parameterized algorithms, Truck scheduling in cross-docking terminals with fixed outbound departures, Exact algorithms for edge domination, Parameterised temporal exploration problems, New exact algorithms for the 2-constraint satisfaction problem, An extremal constrained routing problem with internal losses, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Connected facility location via random facility sampling and core detouring, An alternate formulation of the symmetric traveling salesman problem and its properties, Fast monotone summation over disjoint sets, The deterministic product location problem under a pick-by-order policy, Solving SCS for bounded length strings in fewer than \(2^n\) steps, Problem of optimal choice of a route under conditions of time discounting, Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, An exact algorithm for the minimum dominating clique problem, Minimizing total tardiness in a scheduling problem with a learning effect, Logistics planning of cash transfer to Syrian refugees in Turkey, Invitation to Algorithmic Uses of Inclusion–Exclusion, Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization, Open problems around exact algorithms, Sequencing of picking orders in mobile rack warehouses, On one approach to TSP structural stability, Optimizing automated sorting in warehouses: the minimum order spread sequencing problem, A new upper bound for the traveling salesman problem in cubic graphs, DNA origami and the complexity of Eulerian circuits with turning costs, Exact solution procedures for the balanced unidirectional cyclic layout problem, Restricted dynamic programming: a flexible framework for solving realistic VRPs, Vehicle routing under time-dependent travel times: the impact of congestion avoidance, The travelling salesman problem: selected algorithms and heuristics†, A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem, Scheduling just-in-time part supply for mixed-model assembly lines, Single machine scheduling with nonlinear cost functions, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, Approximation of the double traveling salesman problem with multiple stacks, An interactive multiobjective programming approach to combinatorial data analysis, The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem, Domino sequencing: scheduling with state-based sequence-dependent setup times, On the parameterized tractability of the just-in-time flow-shop scheduling problem, Cluster based branching for the asymmetric traveling salesman problem, Algorithms for the metric ring star problem with fixed edge-cost ratio, Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights, Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks, $$P\mathop{ =}\limits^{?}NP$$, Constrained spanning trees and the traveling salesman problem, A simple linear expected time algorithm for finding a Hamilton path, Tropical Complexity, Sidon Sets, and Dynamic Programming, On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks, Computing in combinatorial optimization, On the fastest finite Markov processes, Material allocation in MRP with tardiness penalties, Parameterized algorithms and complexity for the traveling purchaser problem and its variants, A fair-cost analysis of the random neighbor sampling method, An optimal piecewise-linear program for the U-line balancing problem with stochastic task times, The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, The traveling salesman problem with few inner points, Faster exponential-time algorithms in graphs of bounded average degree, Iterated maximum large neighborhood search for the traveling salesman problem with time windows and its time-dependent version
