Strip packing with precedence constraints and strip packing with release times

DOI10.1016/j.tcs.2009.05.024zbMath1171.68050OpenAlexW1968793818MaRDI QIDQ837172

Sudarshan Banerjee, Sandy Irani, John E. Augustine

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.024

zbMATH Keywords

linear programmingprecedence constraintsapproximation algorithmsfield programmable gate arraystrip packing

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25)

Related Items (8)

A hybrid algorithm for constrained order packing ⋮ Procedures for the bin packing problem with precedence constraints ⋮ Scheduling under the network of temporo-spatial proximity relationships ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ Handling precedence constraints in scheduling problems by the sequence pair representation ⋮ Online bin packing with arbitrary release times

Cites Work

• Unnamed Item
• Shelf algorithms for on-line strip packing
• A new polynomial-time algorithm for linear programming
• Bin packing can be solved within 1+epsilon in linear time
• The ellipsoid method and its consequences in combinatorial optimization
• Resource constrained scheduling as generalized bin packing
• An approximation scheme for strip packing of rectangles with bounded dimensions
• Linear time approximation schemes for vehicle scheduling problems
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• An Exact Approach to the Strip-Packing Problem
• On strip packing With rotations
• Bounds for Assembly Line Balancing Heuristics
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• A algorithm for two-dimensional packing
• Preemptive Scheduling with Release Times, Deadlines, and Due Times
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• OPTVersusLOADin Dynamic Storage Allocation

This page was built for publication: Strip packing with precedence constraints and strip packing with release times