Multiplicity and complexity issues in contemporary production scheduling

DOI10.1111/j.1467-9574.2007.00362.xzbMath1122.90038OpenAlexW2140037720MaRDI QIDQ5422015

Alexander Grigoriev, Joris van de Klundert, Nadia Brauner, Yves Cramer

Publication date: 26 October 2007

Published in: Statistica Neerlandica (Search for Journal in Brave)

Full work available at URL: http://orbi.ulg.ac.be/handle/2268/1710

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Related Items

Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times, An alternative approach for proving the NP-hardness of optimization problems, Identical coupled task scheduling: polynomial complexity of the cyclic case, Throughput optimization in two-machine flowshops with flexible operations, An approximate algorithm for a high-multiplicity parallel machine scheduling problem, Cyclic lot-sizing problems with sequencing costs, Exact and approximate algorithms for high-multiplicity parallel machine scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the number of tardy job units under release time constraints
• On generating all maximal independent sets
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• A polynomial algorithm for an integer quadratic non-separable transportation problem
• On polynomial solvability of the high multiplicity total weighted tardiness problem
• No-wait flow shop scheduling with large lot sizes
• Complexity of one-cycle robotic flow-shops
• The maximum deviation just-in-time scheduling problem.
• On the high multiplicity traveling salesman problem
• A framework for the complexity of high-multiplicity scheduling problems
• A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
• The Traveling Salesman Problem with Many Visits to Few Cities
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• High Multiplicity in Earliness-Tardiness Scheduling
• Minimizing Service and Operation Costs of Periodic Scheduling
• Counting and enumeration complexity with application to multicriteria scheduling
• Makespan minimization for flow-shop problems with transportation times and a single robot