APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS

DOI10.1142/S1793830911001413zbMath1253.68356MaRDI QIDQ2905284

Marin Bougeret, Christina Robenek, Pierre-Francois Dutot, Denis Trystram, Klaus Jansen

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

strip packingmalleable jobsscheduling parallel jobs

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (11)

A faster FPTAS for the unbounded knapsack problem ⋮ A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems ⋮ Peak demand minimization via sliced strip packing ⋮ Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms ⋮ Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing ⋮ Scheduling parallel jobs on heterogeneous platforms ⋮ Complexity and inapproximability results for parallel task scheduling and strip packing ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times ⋮ Weighted completion time minimization for capacitated parallel machines ⋮ New approximability results for two-dimensional bin packing

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• Rectangle packing with one-dimensional resource augmentation
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Fast Approximation Algorithms for Knapsack Problems
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Packing d-Dimensional Bins in d Stages
• Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
• Approximate algorithms to pack rectangles into several strips

This page was built for publication: APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS