Computational complexity of discrete optimization problems

No abstract is available for this paper.

• Publication year

  1977

• Venue

  Annals of discrete mathematics

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0167-5060(08)70821-5
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Complexity of Scheduling under Precedence Constraints

  1978cited by this paper
• `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications

  1978cited by this paper
• Tight bounds for christofides' traveling salesman heuristic

  1978cited by this paper
• The Euclidean Traveling Salesman Problem is NP-Complete

  1977cited by this paper
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

  1977cited by this paper
• Two-Processor Scheduling with Start-Times and Deadlines

  1977cited by this paper
• Fast approximation algorithms for knapsack problems

  1977cited by this paper
• On general routing problems

  1976cited by this paper
• Complexity of decision problems based on finite two-person perfect-information games

  1976cited by this paper
• Some NP-complete geometric problems

  1976cited by this paper
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

  1976cited by this paper
• Approximation algorithms for some routing problems

  1976cited by this paper
• On the complexity of edge traversing

  1976cited by this paper
• A Combinatorial Problem Which Is Complete in Polynomial Space

  1976cited by this paper
• The Complexity of Near-Optimal Graph Coloring

  1976cited by this paper
• Approximation algorithms for combinatorial problems: an annotated bibliography

  1976cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976cited by this paper
• The Complexity of Flowshop and Jobshop Scheduling

  1976cited by this paper
• P-Complete Approximation Problems

  1976cited by this paper
• NP-Complete Scheduling Problems

  1975cited by this paper
• Complexity Results for Multiprocessor Scheduling under Resource Constraints

  1975cited by this paper
• An NP-hard problem in bipartite graphs

  1975cited by this paper
• On the Computational Complexity of Combinatorial Problems

  1975cited by this paper
• Complexity of machine scheduling problems

  1975cited by this paper
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

  1975cited by this paper
• A terminological proposal

  1974cited by this paper
• Matching, Euler tours and the Chinese postman

  1973cited by this paper
• Word problems requiring exponential time(Preliminary Report)

  1973cited by this paper
• Near-optimal bin packing algorithms

  1973cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• HOW GOOD IS THE SIMPLEX ALGORITHM

  1970cited by this paper
• Paths, Trees, and Flowers

  1965cited by this paper
• Parallel Sequencing and Assembly Line Problems

  1961cited by this paper
• An extension of Johnson's results on job IDT scheduling

  1956cited by this paper

• Dynamic and multi-resource flexible job shop scheduling in pharmaceutical manufacturing: A MILP-based decision support tool

  2026cites this paper
• Bipartite Matching with Pair-Dependent Bounds

  2025cites this paper
• Future-Proof Production Scheduling and Control

  2025cites this paper
• Throughput Maximization in a Scheduling Environment with Machine-Dependent Due-Dates

  2025cites this paper
• Complexity Analysis of a Bicriteria Directed Multimodal Transportation Network Design Problem

  2025cites this paper
• Topology-Aware and Highly Generalizable Deep Reinforcement Learning for Efficient Retrieval in Multi-Deep Storage Systems

  2025cites this paper
• Expressivity limits in quantum walk-based optimization

  2025cites this paper
• Optimal design of frame structures with mixed categorical and continuous design variables using the Gumbel–Softmax method

  2024cites this paper
• Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity

  2024cites this paper
• Transgenic Algorithm Applied to the Job Shop Rescheduling Problem

  2024cites this paper
• DAG-based workflows scheduling using Actor-Critic Deep Reinforcement Learning

  2023cites this paper
• Flow shop scheduling of hybrid make-to-stock and make-to-order in a distributed precast concrete production system

  2023cites this paper
• Enabling Astronaut Self-Scheduling using a Robust Advanced Modelling and Scheduling system: an assessment during a Mars analogue mission

  2023cites this paper
• Identifying the promising production planning and scheduling method for manufacturing in Industry 4.0: a literature review

  2023cites this paper
• Two-machine job shop scheduling with optional job rejection

  2023cites this paper
• Graph Representation Learning with Graph Transformers in Neural Combinatorial Optimization

  2023cites this paper
• Variables selection using L0 penalty

  2023cites this paper
• Set-Based Particle Swarm Optimisation: A Review

  2023cites this paper
• Optimum Scheduling of a Multi-Machine Flexible Manufacturing System Considering Job and Tool Transfer Times without Tool Delay

  2023cites this paper
• A Discrete Cooperative Control Method for Production Scheduling Problem of Assembly Manufacturing System

  2023cites this paper
• An Enhanced Adaptive Large Neighborhood Search for Unrelated Parallel Machine Scheduling With Sequence Dependent Setup Times

  2023cites this paper
• Encoding-independent optimization problem formulation for quantum computing

  2023cites this paper
• Cost-Effective Delay-Constrained Optical Fronthaul Design for 5G and Beyond

  2022cites this paper
• Optimum scheduling of machines, automated guided vehicles and tools without tool delay in a multi‐machine flexible manufacturing system using symbiotic organisms search algorithm

  2022influential citation
• Development of scheduling methodology in a multi-machine flexible manufacturing system without tool delay employing flower pollination algorithm

  2022cites this paper
• Fast Algorithm for Solving Extended Flexible Job-Shop Scheduling via Hierarchical Clustering

  2022cites this paper
• A dynamic programming-based heuristic algorithm for a flexible job shop scheduling problem of a matrix system in automotive industry

  2022cites this paper
• Romie: A domain-independent tool for computer-aided robust operations management

  2022cites this paper
• A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources

  2022cites this paper
• An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning

  2022cites this paper
• Instance space analysis and algorithm selection for the job shop scheduling problem

  2022cites this paper
• An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents

  2021cites this paper
• Filter-and-fan approaches for scheduling flexible job shops under workforce constraints

  2021cites this paper
• Resource Constrained Project Scheduling

  2021cites this paper
• Semiconductor final-test scheduling under setup operator constraints

  2021cites this paper
• Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem

  2021cites this paper
• Simultaneous scheduling of machines and tools in a multi machine FMS with alternative routing using symbiotic organisms search algorithm

  2021cites this paper
• Text mining approach for bottleneck detection and analysis in printed circuit board manufacturing

  2021cites this paper
• Integrated simultaneous scheduling of machines, automated guided vehicles and tools in multi machine flexible manufacturing system using symbiotic organisms search algorithm

  2021cites this paper
• A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints

  2021influential citation
• Minimizing the total completion time on a multi-machine FMS using flower pollination algorithm

  2021cites this paper
• A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling : A mixed graph coloring approach

  2021cites this paper
• Elements of Scheduling

  2020cites this paper
• Mixed Graph Colorings: A Historical Review

  2020cites this paper
• Reinforcement Learning on Job Shop Scheduling Problems Using Graph Networks

  2020cites this paper
• Efficient scheduling of a stochastic no-wait job shop with controllable processing times

  2020cites this paper
• A game theory model based on Gale-Shapley for dual-resource constrained (DRC) flexible job shop scheduling

  2020cites this paper
• Efficient algorithms for flexible job shop scheduling with parallel machines

  2020cites this paper
• Vehicle Scheduling Problem

  2020cites this paper
• Graph neural networks-based scheduler for production planning problems using reinforcement learning

  2020influential citation
• Dise\~no e implementaci\'on de una meta-heur\'istica multi-poblacional de optimizaci\'on combinatoria enfocada a la resoluci\'on de problemas de asignaci\'on de rutas a veh\'iculos

  2020cites this paper
• Antiferroelectric Tunnel Junctions as Energy-Efficient Coupled Oscillators: Modeling, Analysis, and Application to Solving Combinatorial Optimization Problems

  2020cites this paper
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem

  2020cites this paper
• Discrete Coordinate Descent (DCD)

  2020cites this paper
• Scheduling of Real-Time Tasks With Multiple Critical Sections in Multiprocessor Systems

  2020influential citation
• CONVJSSP: Convolutional Learning for Job-Shop Scheduling Problems

  2020cites this paper
• A Robust Knapsack Based Constrained Portfolio Optimization

  2020cites this paper
• On the Integration of Unmanned Aerial Vehicles into Public Airspace

  2020cites this paper
• Adopted rescheduling strategy for solving the dynamic job shop using GA based Local Search

  2019cites this paper
• Machine Learning for Constraint Programming

  2019cites this paper
• Optimized Resource Allocations in Business Process Models

  2019cites this paper
• Graph colouring variations

  2019cites this paper
• A NSGA-II Algorithm Hybridizing Local Simulated-Annealing Operators for a Bi-Criteria Robust Job-Shop Scheduling Problem Under Scenarios

  2019cites this paper
• Scheduling in Job Shops

  2019cites this paper
• Mathematical Models for a Flexible Job Shop Scheduling Problem with Machine Operator Constraints

  2019cites this paper
• Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems

  2019cites this paper
• Energy-Aware Speculative Execution in Vehicular Edge Computing Systems

  2019cites this paper
• Models and algorithms for online stochastic vehicle routing problems. (Modèles et algorithmes pour des problèmes de routage de véhicules en ligne et stochastiques)

  2019cites this paper
• Problèmes d'ordonnancement et de moyens de transport des systèmes de production: prise en compte de la qualité de service. (Scheduling and routing problems in production systems: taking quality of service into consideration)

  2019cites this paper
• Integrated scheduling of machines, AGVs and tools in multi-machine FMS using crow search algorithm

  2019cites this paper
• Scheduling Mutual Exclusion Accesses in Equal-Length Jobs

  2019cites this paper
• Reinforcement Learning Based VNF Scheduling with End-to-End Delay Guarantee

  2019influential citation
• Active Learning Methods for Dynamic Job Shop Scheduling using Genetic Programming under Uncertain Environment

  2019cites this paper
• Soft Constraints in MiniBrass: Foundations and Applications

  2019cites this paper
• Solving the no-wait job shop scheduling problem with due date constraints: A problem transformation approach

  2019cites this paper
• Bad-scenario-set robust scheduling for a job shop to hedge against processing time uncertainty

  2018cites this paper
• A worker constrained flexible job shop scheduling problem with sequence-dependent setup times

  2018cites this paper
• An Improved Genetic Algorithm with Local Search for Solving the DJSSP with New Dynamic Events

  2018cites this paper
• A Dial-a-Ride evaluation for solving the job-shop with routing considerations

  2018cites this paper
• A hybrid local-search algorithm for robust job-shop scheduling under scenarios

  2018cites this paper
• Joint production and transportation scheduling in flexible manufacturing systems

  2018cites this paper
• A worker constrained flexible job shop scheduling problem with sequence-dependent setup times

  2018cites this paper
• A new exact algorithm for no-wait job shop problem to minimize makespan

  2018cites this paper
• Controlling a Single Transport Robot in a Flexible Job Shop Environment by Hybrid Metaheuristics

  2018cites this paper
• Low-Complexity Approximate Convolutional Neural Networks

  2018cites this paper
• Joint production and transportation scheduling in flexible manufacturing systems

  2018cites this paper
• Mixed graph colouring for unit-time scheduling

  2017cites this paper
• Strengths and Limitations of Linear Programming Relaxations

  2017cites this paper
• A State-of-the-art Review of Job-Shop Scheduling Techniques

  2017cites this paper
• Bad-scenario-set robust optimization framework with two objectives for uncertain scheduling systems

  2017cites this paper
• Complexity, bounds and dynamic programming algorithms for single track train scheduling

  2017cites this paper
• On the exact solution of the no-wait flow shop problem with due date constraints

  2017cites this paper
• Minimizing the worst-case makespan for a job-shop scheduling system with uncertain processing times

  2017cites this paper
• Solving comprehensive dynamic job shop scheduling problem by using a GRASP-based approach

  2017cites this paper
• A Novel Structure to Realize Memory Cell Fluctuation Under Voltage Control in Ising Chip

  2017cites this paper
• Parameterized complexity of machine scheduling: 15 open problems

  2017cites this paper
• Understanding Complexity in a Practical Combinatorial Problem Using Mathematical Programming and Constraint Programming

  2017cites this paper
• Hybrid metaheuristics for scheduling of machines and transport robots in job shop environment

  2016cites this paper
• Output Rate Variation Problem: Some Heuristic Paradigms and Dynamic Programming

  2016cites this paper
• An Improved Quantum-Inspired Evolution Algorithm for No-Wait Flow Shop Scheduling Problem to Minimize Makespan

  2016cites this paper