A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
From MaRDI portal
Publication:2757667
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
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
Unnamed Item, 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, Fixed-parameter tractability for the Tree Assembly problem, 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