Orthogonal Packings in Two Dimensions
From MaRDI portal
Publication:3893334
DOI10.1137/0209064zbMath0447.68080OpenAlexW2019318803WikidataQ56813845 ScholiaQ56813845MaRDI QIDQ3893334
Ronald L. Rivest, Brenda S. Baker, Edward G. jun. Coffman
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209064
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
A mathematical model and a solution method for the problem of placing various-sized circles into a strip, Shelf algorithms for on-line strip packing, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, Strip packing with precedence constraints and strip packing with release times, A hybrid evolutionary algorithm for the two-dimensional packing problem, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints, The nesting problem in the leather manufacturing industry, A new lower bound for online strip packing, Resource sharing combined with layout effects in high-level synthesis, Polynomial-time approximation schemes for circle and other packing problems, An effective shaking procedure for 2D and 3D strip packing problems, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, Efficient implementations of construction heuristics for the rectilinear block packing problem, An effective tabu search approach with improved loading algorithms for the 3L-CVRP, Exhaustive approaches to 2D rectangular perfect packings, An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation, An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules, A simple randomized algorithm for two-dimensional strip packing, An exact strip packing algorithm based on canonical forms, Models and algorithms for packing rectangles into the smallest square, A tight analysis of Brown-Baker-Katseff sequences for online strip packing, Exact and approximate methods for parallel multiple-area spatial scheduling with release times, Efficient heuristics for robot acquisition planning for a CIM system, New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Approximation and online algorithms for multidimensional bin packing: a survey, Corner occupying theorem for the two-dimensional integral rectangle packing problem, A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem, Expected performance of the shelf heuristic for 2-dimensional packing, iGreen: green scheduling for peak demand minimization, Scheduling parallel jobs to minimize the makespan, An approximation scheme for strip packing of rectangles with bounded dimensions, A reference length approach for the 3D strip packing problem, Space defragmentation for packing problems, New perspectives in VLSI design automation: deterministic packing by sequence pair, Routing problems with loading constraints, A \((5/3+\varepsilon)\)-approximation for strip packing, Simulated annealing for manufacturing systems layout design, An exact algorithm for general, orthogonal, two-dimensional knapsack problems, A 2.5 times optimal algorithm for packing in two dimensions, Improved upper bounds for online malleable job scheduling, Online multiple-strip packing, A hybrid placement strategy for the three-dimensional strip packing problem, A squeaky wheel optimisation methodology for two-dimensional strip packing, An improved BL lower bound, A skyline heuristic for the 2D rectangular packing and strip packing problems, Probabilistic analysis for simple one- and two-dimensional bin packing algorithms, Exact algorithms for the guillotine strip cutting/packing problem., An effective approximation algorithm for the malleable parallel task scheduling problem, Dealing with nonregular shapes packing, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem, Packing, covering and tiling in two-dimensional spaces, Online square packing with gravity, Reactive GRASP for the strip-packing problem, A multi-objective genetic algorithm for a special type of 2D orthogonal packing problems, Oriented aligned rectangle packing problem, On-line scheduling of parallel jobs in a list, Knowledge based approach to the cutting stock problem, A parallel biased random-key genetic algorithm with multiple populations applied to irregular strip packing problems, Spatial scheduling optimization algorithm for block assembly in shipbuilding, New upper bounds for online strip packing, Packing problems, A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint, An efficient deterministic heuristic for two-dimensional rectangular packing, Recent advances on two-dimensional bin packing problems, A 3-approximation algorithm for two-dimensional bin packing, Human-guided search, A new upper bound for the online square packing problem in a strip, Bidirectional best-fit heuristic for orthogonal rectangular strip packing, The two-dimensional cutting stock problem revisited, Average-case performance analysis of a 2D strip packing algorithm -- NFDH, Vehicle routing problems with loading constraints: state-of-the-art and future directions, Improved approximation for two dimensional strip packing with polynomial bounded width, A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks, Exact solution techniques for two-dimensional cutting and packing, The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio, Two-bar charts packing problem, Malleable scheduling for flows of jobs and applications to MapReduce, On genetic algorithms for the packing of polygons, An open space based heuristic for the 2D strip packing problem with unloading constraints, Exact algorithms for the two-dimensional strip packing problem with and without rotations, A note on online strip packing, A hybrid metaheuristic for the two-dimensional strip packing problem, Metaheuristics for vehicle routing problems with three-dimensional loading constraints, Packing solar cells on a roof, Bubblesearch: a simple heuristic for improving priority-based greedy algorithms, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, An algorithm for polygon placement using a bottom-left strategy, Two-dimensional packing problems: a survey, An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle, Network flows and non-guillotine cutting patterns, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, An algorithm for the 2D guillotine cutting stock problem, Improved lower bound for online strip packing, Two-dimensional packing algorithms for layout of disconnected graphs, The variable-width strip packing problem, Scheduling space-sharing for internet advertising, Effective loading in combined vehicle routing and container loading problems, A computational study of constraint programming approaches for resource-constrained project scheduling with autonomous learning effects, A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints, Coordination Mechanisms for Selfish Parallel Jobs Scheduling, A Posteriori Analysis of the Algorithms for Two-Bar Charts Packing Problem, On two dimensional packing, Online Square Packing, Two for One: Tight Approximation of 2D Bin Packing, A new exact method for the two-dimensional orthogonal packing problem, Efficiency of two classes of dynamic scheduling algorithms in multiprocessor computer systems, The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview, On-line bin packing ? A restricted survey, Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle, A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing, An introduction to the two‐dimensional rectangular cutting and packing problem, Rectangle packing with a recursive pilot method, Peak demand minimization via sliced strip packing, An improved approximation algorithm for scheduling monotonic moldable tasks, Cargo securing under multi-drop and axle weight constraints, High multiplicity strip packing with three rectangle types, Improved sequential insertion heuristics for berth allocation problems, Solution validator and visualizer for (combined) vehicle routing and container loading problems, Unnamed Item, An improved approximation for packing big two-bar charts, Ship Traffic Optimization for the Kiel Canal, Asymptotically optimal scheduling of random malleable demands in smart grid, A Tight (3/2+ε) Approximation for Skewed Strip Packing., TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING, Dynamic storage allocation with known durations, Fuzzy bin packing problem., Online strip packing with modifiable boxes, On-line algorithms for packing rectangles into several strips, Complexity and inapproximability results for parallel task scheduling and strip packing, A fast implementation for the 2D/3D box placement problem, An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem, Upper bounds for heuristic approaches to the strip packing problem, Closing the Gap for Pseudo-Polynomial Strip Packing, Probabilistic analysis of shelf algorithms for strip packing, Approximate algorithms to pack rectangles into several strips, An improved best-fit heuristic for the orthogonal strip packing problem, Adjacent-Resource Scheduling, On Packing Two-Dimensional Bins