A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths

DOI10.1287/moor.26.1.31.10590zbMath1073.90513MaRDI QIDQ2757667

S. Thomas McCormick, Scott R. Smallwood, Frits C. R. Spieksma

Publication date: 26 November 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.26.1.31.10590

zbMATH Keywords

Parallel machine scheduling, high-multiplicity scheduling, polynomial algorithms, bin packing, cutting stock, Hilbert basis, integer roundup property, integer decomposition property

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Multiplicity and complexity issues in contemporary production scheduling, Matching with sizes (or scheduling with processing set restrictions), Matching with sizes (or scheduling with processing set restrictions), Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory, Optimal packet-to-slot assignment in mobile telecommunications, Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions, On the bin packing problem with a fixed number of object weights, Polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems, More on online bin packing with two item sizes, An approximate algorithm for a high-multiplicity parallel machine scheduling problem, Exact and approximate algorithms for high-multiplicity parallel machine scheduling, Carathéodory bounds for integer cones, Packet scheduling in third-generation mobile systems with UTRA-TDD air interface, A framework for the complexity of high-multiplicity scheduling problems, An asymptotically exact algorithm for the high-multiplicity bin packing problem