A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths

DOI10.1287/moor.26.1.31.10590zbMath1073.90513OpenAlexW2162870855MaRDI 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

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Optimal packet-to-slot assignment in mobile telecommunications ⋮ Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions ⋮ Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ 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 ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ Fixed-parameter tractability for the Tree Assembly problem ⋮ More on online bin packing with two item sizes ⋮ Carathéodory bounds for integer cones ⋮ Packet scheduling in third-generation mobile systems with UTRA-TDD air interface ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ Unnamed Item ⋮ An approximate algorithm for a high-multiplicity parallel machine scheduling problem ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ A framework for the complexity of high-multiplicity scheduling problems ⋮ An asymptotically exact algorithm for the high-multiplicity bin packing problem

This page was built for publication: A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths