Online multiple-strip packing

DOI10.1016/j.tcs.2009.09.029zbMath1207.90086OpenAlexW2099175830MaRDI QIDQ621841

Xin Han, Deshi Ye, Guo-Chuan Zhang

Publication date: 28 January 2011

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

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

zbMATH Keywords

approximation algorithmsstrip packingmany-core scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Coordination Mechanisms for Selfish Parallel Jobs Scheduling ⋮ A new lower bound for online strip packing ⋮ Approximate composable truthful mechanism design ⋮ Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem ⋮ The generalization of scheduling with machine cost ⋮ Unnamed Item ⋮ On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis ⋮ Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing ⋮ New upper bounds for online strip packing

Cites Work

• Shelf algorithms for on-line strip packing
• Online scheduling of parallel jobs on two machines is 2-competitive
• On-line scheduling of parallel jobs in a list
• A note on online strip packing
• Incremental medians via online bidding
• Shelf Algorithms for Two-Dimensional Packing Problems
• Complexity of Scheduling Parallel Task Systems
• Orthogonal Packings in Two Dimensions
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Online Algorithm for Parallel Job Scheduling and Strip Packing
• Approximate algorithms to pack rectangles into several strips
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Online multiple-strip packing