A linear time algorithm for restricted bin packing and scheduling problems

DOI10.1016/0167-6377(83)90042-1zbMath0507.90046OpenAlexW2065394292MaRDI 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 algorithmbin packingtask schedulingfinite set of possible weights of elements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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