Computational Complexity of Discrete Optimization Problems

DOI10.1016/S0167-5060(08)70821-5zbMATH Open0411.68042MaRDI QIDQ4198060FDOQ4198060

Alexander H. G. Rinnooy Kan, Jan Karel Lenstra

Publication date: 1979

Published in: Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium (Search for Journal in Brave)

zbMATH Keywords

linear programming problemcombinatorial problemcomputational complexity, discrete optimization problemreducibility among problems, Np-completeness

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cited In (68)

• The robot sequencing problem: polynomial algorithm and complexity
• A new lower bound for the job-shop scheduling problem
• List scheduling algorithms to minimize the makespan on identical parallel machines
• Job shop scheduling with unit time operations under resource constraints and release dates
• Complexity, bounds and dynamic programming algorithms for single track train scheduling
• Semiconductor final-test scheduling under setup operator constraints
• An exact algorithm for the identical parallel machine scheduling problem.
• A worker constrained flexible job shop scheduling problem with sequence-dependent setup times
• Task scheduling with and without communication delays: A unified approach
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job
• Scheduling subject to nonrenewable-resource constraints
• Towards Tight Lower Bounds for Scheduling Problems
• Parameterized complexity of machine scheduling: 15 open problems
• Hybrid rollout approaches for the job shop scheduling problem
• A new hybrid parallel genetic algorithm for the job‐shop scheduling problem
• Scheduling the truckload operations in automatic warehouses
• Complexity analysis of job-shop scheduling with deteriorating jobs
• An efficient algorithm for a job shop problem
• Is a unit-job shop not easier than identical parallel machines?
• A note on flow-shop and job-shop batch scheduling with identical processing-time jobs
• Arc-B-consistency of the inter-distance constraint
• Batch scheduling on two-machine flowshop with machine-dependent setup times
• On the exact solution of the no-wait flow shop problem with due date constraints
• An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling
• Complete local search with limited memory algorithm for no-wait job shops to minimize makespan
• A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles
• No-wait job shop scheduling: tabu search and complexity of subproblems
• A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
• Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms
• Complexity of mixed shop scheduling problems: A survey
• Job-shop scheduling with processing alternatives.
• An appraisal of computational complexity for operations researchers
• An effective lower bound on \(L_{\max}\) in a worker-constrained job shop
• Solving the job-shop scheduling problem optimally by dynamic programming
• Adaptive temperature control for simulated annealing: a comparative study
• Instance space analysis and algorithm selection for the job shop scheduling problem
• Complexity results for scheduling chains on a single machine
• An enhanced timetabling procedure for the no-wait job shop problem: a complete local search approach
• Surrogate duality relaxation for job shop scheduling
• Open-shop batch scheduling with identical jobs
• A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem
• The job shop scheduling problem: Conventional and new solution techniques
• A study on several combination problems of classic shop scheduling and shortest path
• Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
• Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem
• Deterministic job-shop scheduling: Past, present and future
• Batch scheduling on a two-machine jobshop with machine-dependent setup times
• Minimizing maximum lateness in a two-machine unit-time job shop
• Approximative procedures for no-wait job shop scheduling.
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic
• On scheduling cycle shops: Classification, complexity and approximation
• On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion
• Evolution based learning in a job shop scheduling environment
• A hybrid genetic algorithm for the job shop scheduling problem
• Joint production and transportation scheduling in flexible manufacturing systems
• Efficient algorithms for flexible job shop scheduling with parallel machines
• On the power of randomization for job shop scheduling withk-units length tasks
• Variables selection using \(\mathcal{L}_0\) penalty
• Output Rate Variation Problem: Some Heuristic Paradigms and Dynamic Programming
• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach
• A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
• An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning
• Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms
• Mixed graph colouring as scheduling multi-processor tasks with equal processing times
• A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources

This page was built for publication: Computational Complexity of Discrete Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4198060)