Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
From MaRDI portal
Publication:5331678
DOI10.1287/opre.12.5.655zbMath0126.36006OpenAlexW2044060832WikidataQ56019908 ScholiaQ56019908MaRDI QIDQ5331678
Paul C. Gilmore, Ralph E. Gomory
Publication date: 1964
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.12.5.655
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35)
Related Items
Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking, Some no-wait shops scheduling problems: Complexity aspect, Two-stage hybrid flowshop scheduling with simultaneous processing machines, Scheduling electric vehicles and locating charging stations on a path, Recognition of Gilmore-Gomory traveling salesman problem, Twin-crane scheduling during seaside workload peaks with a dedicated handshake area, Flow shop scheduling with flexible processing times, Three-machine flow shop scheduling with overlapping waiting time constraints, Greedy concepts for network flow problems, The two-machine no-wait general and proportionate open shop makespan problem, Some complexity results in cyclic scheduling, Complexity of flow shop scheduling problems with transportation constraints, Cyclic flow-shop scheduling with no-wait constraints and missing operations, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Different behaviour of a double branch-and-bound algorithm on \(\mathrm {Fm}|\mathrm{prmu}|C_{\max}\) and \(\mathrm {Fm}|\mathrm {block}|C_{\max}\) problems, Optimizing blocking flow shop scheduling problem with total completion time criterion, Lot sizing in a no-wait flow shop, Two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption, On no-wait and no-idle flow shops with makespan criterion, A variant of the permutation flow shop model with variable processing times, On permutation schedules for two-machine flow shops with buffer constraints and constant processing times on one machine, Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times, A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan, Solution algorithms for synchronous flow shop problems with two dominating machines, Efficiently solvable special cases of hard combinatorial optimization problems, Container supply with multi-trailer trucks: parking strategies to speed up the gantry crane-based loading of freight trains in rail yards, A new asymmetric pyramidally solvable class of the traveling salesman problem, An algorithm for the detection and construction of Monge sequences, Two-stage no-wait scheduling models with setup and removal times separated, Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines, Applications of max-plus algebra to flow shop scheduling problems, Approximating the 2-machine flow shop problem with exact delays taking two values, Scheduling in reentrant robotic cells: algorithms and complexity, Sequencing and scheduling in robotic cells: recent developments, Two-machine stochastic flow shops with blocking and the traveling salesman problem, Shortest common superstrings and scheduling with coordinated starting times, Minimizing sequence-dependent setup costs in feeding batch processes under due date restrictions, On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices, Interference aware scheduling of triple-crossover-cranes, Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility, An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers., On Gilmore-Gomory's open question for the bottleneck TSP., Approximability of two-machine no-wait flowshop scheduling with availability constraints., Crane scheduling in railway yards: an analysis of computational complexity, Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times., Blocking systems of a graph and intersection-union interchange equality in bottleneck problems involving sets and fuzzy sets, Exact methods for the robotic cell problem, Improved bounded dynamic programming algorithm for solving the blocking flow shop problem, A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop, A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time, Batch scheduling in a two-machine flow shop with limited buffer, Four decades of research on the open-shop scheduling problem to minimize the makespan, \(\mathrm{A}^\ast\) search for prize-collecting job sequencing with one common and multiple secondary resources, The traveling salesman problem: An overview of exact and approximate algorithms, Minimizing the number of workers in a paced mixed-model assembly line, Experimental analysis of heuristics for the bottleneck traveling salesman problem, Decomposition algorithms for synchronous flow shop problems with additional resources and setup times, Monge and feasibility sequences in general flow problems, A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations, The \(x\)-and-\(y\)-axes travelling salesman problem, Inapproximability results for no-wait job shop scheduling., Match twice and stitch: a new TSP tour construction heuristic., Minimum deviation algorithm for two-stage no-wait flowshops with parallel machines, An efficient optimal solution to the coil sequencing problem in electro-galvanizing line, Scheduling two-machine no-wait open shops to minimize makespan, Throughput optimization in two-machine flowshops with flexible operations, Two-machine flow shop scheduling problems with no-wait jobs, Scheduling algorithms for flexible flowshops: Worst and average case performance, The forgotten sons: warehousing systems for brick-and-mortar retail chains, Synchronous flow shop scheduling with pliable jobs, Complexity results for flow shop problems with synchronous movement, Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds, Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood, Minimizing makespan for a no-wait flowshop using genetic algorithm, No-wait two-stage flowshop problem with multi-task flexibility of the first machine, The two-machine total completion time flow shop problem, An approximation algorithm for a bottleneck traveling salesman problem, The flow shop problem with no-idle constraints: a review and approximation, An empirical analysis of the optimality rate of flow shop heuristics, \(\frac{3}{2}\)-approximation for two-machine no-wait flowshop scheduling with availability constraints, Cyclic scheduling in 3-machine robotic flow shops, A two-machine no-wait flow shop problem with two competing agents, An optimization-based heuristic for the robotic cell problem, A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups, Minimizing makespan in a pallet-constrained flowshop, Sequencing of jobs in some production system, An equivalency problem in discrete programming over ordered semigroups, Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems, The optimum assignments and a new heuristic approach for the traveling salesman problem, Small and large TSP: Two polynomially solvable cases of the traveling salesman problem, Two-machine group scheduling problem with blocking and anticipatory setups, Dynamic sequencing of robot moves in a manufactoring cell, The complexity of scheduling jobs in repetitive manufacturing systems, Performance of scheduling algorithms for no-wait flowshops with parallel machines, An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices, Optimal control of a class of DEDS: Flow-shops with state-dependent processing times, Domination analysis of some heuristics for the traveling salesman problem, New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization, Heuristics for two-machine no-wait flowshop scheduling with an availability constraint, A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, When road trains supply freight trains: scheduling the container loading process by gantry crane between multi-trailer trucks and freight trains, Optimal versus heuristic scheduling of surface mount technology lines, Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs, Special cases of travelling salesman problems and heuristics, Some local search algorithms for no-wait flow-shop problem with makespan criterion, Scheduling in supply chain environment, On non-permutation solutions to some two machine flow shop scheduling problems, Flowshop sequencing problems with limited buffer storage, Some problems in discrete optimization, How to charge while driving: scheduling point-to-point deliveries of an electric vehicle under overhead wiring, A solvable case of the traveling salesman problem, No-Wait Scheduling Problems with Batching Machines, Unnamed Item, Monge properties, discrete convexity and applications, On Eulerian extensions and their application to no-wait flowshop scheduling, Routing equal-size messages on a slotted ring, Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications, Improved bounds for open online dial-a-ride on the line, Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line, Unnamed Item, Some new results in flow shop scheduling, Two-stage hybrid flow shop with recirculation, Part sequencing in three-machine no-wait robotic cells, An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops, An exact method for scheduling a yard crane, GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY, Batch scheduling in the no-wait two-machine flowshop to minimize the makespan, Flow shop-sequencing problem with synchronous transfers and makespan minimization, Scheduling parallel machines with a single server: Some solvable cases and heuristics, Unnamed Item, Coupled task scheduling with exact delays: literature review and models, No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem, Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm, Domino sequencing: scheduling with state-based sequence-dependent setup times, COMPARISON OF SCHEDULING EFFICIENCY IN TWO/THREE-MACHINE NO-WAIT FLOW SHOP PROBLEM USING SIMULATED ANNEALING AND GENETIC ALGORITHM, Scheduling production tasks in a two-stage FMS, Minimax 2-connected subgraphs and the bottleneck traveling salesman problem, Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths, Scheduling two parallel machines with a single server: the general case, A review of TSP based approaches for flowshop scheduling, Complexity of flowshop scheduling problems with a new blocking constraint, Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices, SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS, Sequencing of robot activities and parts in two-machine robotic cells, Permutation flowshop scheduling problems with maximal and minimal time lags
