Resource constrained scheduling as generalized bin packing

DOI10.1016/0097-3165(76)90001-7zbMath0384.90053WikidataQ89142680 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

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach, A bin packing game with cardinality constraints under the best cost rule, Dynamic Packing with Side Constraints for Datacenter Resource Management, TOC-based planning and scheduling model, Sequential selection of random vectors under a sum constraint, On-line bin packing ? A restricted survey, Unnamed Item, Unnamed Item, Analysis of a first-fit algorithm for the capacitated unit covering problem, Lower bounds and algorithms for the 2-dimensional vector packing problem, On-line scheduling of parallel jobs with runtime restrictions, Streaming algorithms for bin packing and vector scheduling, There is no asymptotic PTAS for two-dimensional vector packing, Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem, A single machine scheduling problem with two-dimensional vector packing constraints, Procedures for the bin packing problem with precedence constraints, Vector bin packing with heterogeneous bins: application to the machine reassignment problem, The load-balanced multi-dimensional bin-packing problem, Vector bin packing with multiple-choice, On the absolute approximation ratio for first fit and related results, Tighter bounds of the First Fit algorithm for the bin-packing problem, Approximation algorithms for time constrained scheduling, Resource scheduling with variable requirements over time, Strip packing with precedence constraints and strip packing with release times, The generalized assignment problem: Valid inequalities and facets, Online interval coloring with packing constraints, On lazy bin covering and packing problems, The poset scheduling problem, Bin packing with divisible item sizes, List scheduling bounds for UET systems with resources, Bin packing can be solved within 1+epsilon in linear time, Assembly line balancing as generalized bin packing, Repacking helps in bounded space on-line bin-packing, Bounds on list scheduling of UET tasks with restricted resource constraints, Properties of some ILP formulations of a class of partitioning problems, A branch-and-bound algorithm for the two-dimensional vector packing problem, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, Tight approximations for resource constrained scheduling and bin packing, Approximate strong separation with application in fractional graph coloring and preemptive scheduling., The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints, Bin packing game with a price of anarchy of \(\frac{3}{2}\), Offline first-fit decreasing height scheduling of power loads, Exact and approximation algorithms for geometric and capacitated set cover problems, A linear time algorithm for restricted bin packing and scheduling problems, An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing, Algorithms for on-line bin-packing problems with cardinality constraints, Worst-case analysis of the FFH algorithm for online variable-sized bin packing, Selfish vector packing, Online bin packing with cardinality constraints resolved, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, The tight absolute bound of First Fit in the parameterized case, Parallel machine scheduling with additional resources: notation, classification, models and solution methods, Improved approximation algorithms for maximum resource bin packing and lazy bin covering problems, A two-dimensional vector packing model for the efficient use of coil cassettes, A note on a selfish bin packing problem, Approximation and online algorithms for multidimensional bin packing: a survey, Scheduling selfish jobs on multidimensional parallel machines, Bounds for online bin packing with cardinality constraints, Selfish Vector Packing, A Framework for Distributing Real-Time Functions, On Packing Two-Dimensional Bins, A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing, Scheduling unit-time tasks in renewable resource constrained flowshops, Approximation scheduling algorithms: a survey

Cites Work