Resource constrained scheduling as generalized bin packing
From MaRDI portal
Publication:1249132
DOI10.1016/0097-3165(76)90001-7zbMath0384.90053OpenAlexW2025787252WikidataQ89142680 ScholiaQ89142680MaRDI QIDQ1249132
Ronald L. Graham, Andrew Chi-Chih Yao, David S. Johnson, Michael R. Garey
Publication date: 1976
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0097-3165(76)90001-7
Related Items
Multiple-type, two-dimensional bin packing problems: Applications and algorithms, There is no asymptotic PTAS for two-dimensional vector packing, Resource scheduling with variable requirements over time, Algorithms for on-line bin-packing problems with cardinality constraints, Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem, Strip packing with precedence constraints and strip packing with release times, Bounds for online bin packing with cardinality constraints, The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints, Selfish Vector Packing, Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems, A single machine scheduling problem with two-dimensional vector packing constraints, Procedures for the bin packing problem with precedence constraints, Bin packing with divisible item sizes, A two-dimensional vector packing model for the efficient use of coil cassettes, Sequential selection of random vectors under a sum constraint, Vector bin packing with heterogeneous bins: application to the machine reassignment problem, The load-balanced multi-dimensional bin-packing problem, A note on a selfish bin packing problem, Worst-case analysis of the FFH algorithm for online variable-sized bin packing, Tight approximations for resource constrained scheduling and bin packing, Approximation and online algorithms for multidimensional bin packing: a survey, Scheduling selfish jobs on multidimensional parallel machines, Tighter bounds of the First Fit algorithm for the bin-packing problem, On-line bin packing ? A restricted survey, Online bin packing with cardinality constraints resolved, List scheduling bounds for UET systems with resources, Scheduling unit-time tasks in renewable resource constrained flowshops, Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows, Approximate strong separation with application in fractional graph coloring and preemptive scheduling., A 4/3 OPT+2/3 approximation for big two-bar charts packing problem, Vector bin packing with multiple-choice, The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers, Online two-dimensional vector packing with advice, Bin packing game with a price of anarchy of \(\frac{3}{2}\), The generalized assignment problem: Valid inequalities and facets, Offline first-fit decreasing height scheduling of power loads, On the absolute approximation ratio for first fit and related results, Bin packing can be solved within 1+epsilon in linear time, Assembly line balancing as generalized bin packing, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, A Framework for Distributing Real-Time Functions, A bin packing game with cardinality constraints under the best cost rule, Dynamic Packing with Side Constraints for Datacenter Resource Management, Selfish vector packing, Approximation algorithms for time constrained scheduling, Online interval coloring with packing constraints, Exact and approximation algorithms for geometric and capacitated set cover problems, Repacking helps in bounded space on-line bin-packing, Lower bounds and algorithms for the 2-dimensional vector packing problem, TOC-based planning and scheduling model, Unnamed Item, On-line scheduling of parallel jobs with runtime restrictions, Unnamed Item, Streaming algorithms for bin packing and vector scheduling, Bounds on list scheduling of UET tasks with restricted resource constraints, Analysis of a first-fit algorithm for the capacitated unit covering problem, Properties of some ILP formulations of a class of partitioning problems, Approximation scheduling algorithms: a survey, On lazy bin covering and packing problems, A linear time algorithm for restricted bin packing and scheduling problems, Online Submodular Maximization Problem with Vector Packing Constraint., Packing-based branch-and-bound for discrete malleable task scheduling, Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach, The poset scheduling problem, A branch-and-bound algorithm for the two-dimensional vector packing problem, Adaptive Bin Packing with Overflow, On Packing Two-Dimensional Bins, The tight absolute bound of First Fit in the parameterized case, An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing, Parallel machine scheduling with additional resources: notation, classification, models and solution methods, A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for combinatorial problems
- Fast algorithms for bin packing
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
- Bounds for Multiprocessor Scheduling with Resource Constraints
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
