Shelf Algorithms for Two-Dimensional Packing Problems

DOI10.1137/0212033zbMath0521.68084OpenAlexW2081987145MaRDI QIDQ3670602

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212033

zbMATH Keywords

scheduling approximation algorithms bin-packing orthogonal packing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)

Related Items (46)

Shelf algorithms for on-line strip packing ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ Coordination Mechanisms for Selfish Parallel Jobs Scheduling ⋮ Approximate strip packing: revisited ⋮ Scheduling non-preemptible jobs to minimize peak demand ⋮ An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem ⋮ The nesting problem in the leather manufacturing industry ⋮ A new lower bound for online strip packing ⋮ Efficient heuristics for robot acquisition planning for a CIM system ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Expected performance of the shelf heuristic for 2-dimensional packing ⋮ Multidimensional on-line bin packing: Algorithms and worst-case analysis ⋮ iGreen: green scheduling for peak demand minimization ⋮ An Exact Algorithm for Non-preemptive Peak Demand Job Scheduling ⋮ On-line bin packing ? A restricted survey ⋮ The generalization of scheduling with machine cost ⋮ Online multiple-strip packing ⋮ Improved online algorithms for parallel job scheduling and strip packing ⋮ Unnamed Item ⋮ On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis ⋮ Online square packing with gravity ⋮ On the effectiveness of the harmonic shelf algorithm for on-line strip packing ⋮ Oriented aligned rectangle packing problem ⋮ WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION ⋮ On-line scheduling of parallel jobs in a list ⋮ Knowledge based approach to the cutting stock problem ⋮ New upper bounds for online strip packing ⋮ Packing problems ⋮ On some packing problem related to dynamic storage allocation ⋮ Dynamic storage allocation with known durations ⋮ Recent advances on two-dimensional bin packing problems ⋮ Packings in two dimensions: Asymptotic average-case analysis of algorithms ⋮ A new upper bound for the online square packing problem in a strip ⋮ The two-dimensional cutting stock problem revisited ⋮ Online strip packing with modifiable boxes ⋮ On-line algorithms for packing rectangles into several strips ⋮ Average-case analysis of cutting and packing in two dimensions ⋮ Online Algorithm for Parallel Job Scheduling and Strip Packing ⋮ A note on online strip packing ⋮ Online scheduling of moldable parallel tasks ⋮ Probabilistic analysis of shelf algorithms for strip packing ⋮ Techniques and results on approximation algorithms for packing circles ⋮ AN EFFICIENT JOB SCHEDULING ALGORITHM IN PARTITIONABLE MESH CONNECTED SYSTEMS ⋮ Improved lower bound for online strip packing ⋮ The variable-width strip packing problem ⋮ Scheduling space-sharing for internet advertising

This page was built for publication: Shelf Algorithms for Two-Dimensional Packing Problems