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