A linear time algorithm for restricted bin packing and scheduling problems

DOI10.1016/0167-6377(83)90042-1zbMath0507.90046MaRDI QIDQ1837623

Klaus H. Ecker, Jacek Błażewicz

Publication date: 1983

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(83)90042-1

zbMATH Keywords

linear time algorithm; bin packing; task scheduling; finite set of possible weights of elements

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B35: Deterministic scheduling theory in operations research

Related Items

Online bin packing with advice, Unit-time scheduling problems with time dependent resources, Scheduling tasks on two processors with deadlines and additional resources, Minimizing mean flow time with parallel processors and resource constraints, New trends in machine scheduling, Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems, Algorithms for minimizing maximum lateness with unit length tasks and resource constraints, Parallel machine scheduling with additional resources: notation, classification, models and solution methods, Scheduling: agreement graph vs resource constraints

Cites Work

• Scheduling subject to resource constraints: Classification and complexity
• Bin packing can be solved within 1+epsilon in linear time
• Resource constrained scheduling as generalized bin packing
• Deadline scheduling of tasks with ready times and resource constraints
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item