Multiplicity and complexity issues in contemporary production scheduling

DOI10.1111/j.1467-9574.2007.00362.xzbMath1122.90038MaRDI 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

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

90B10: Deterministic network models in operations research

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, Exact and approximate algorithms for high-multiplicity parallel machine scheduling, Cyclic lot-sizing problems with sequencing costs

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