Bin packing with restricted piece sizes

DOI10.1016/0020-0190(89)90223-8MaRDI QIDQ1825652zbMATH OpenOpenAlexFDO

Authors Joseph Y.-T. Leung

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90223-8

zbMATH Keywords

strongly NP-hardmultiprocessor scheduling problem\(\epsilon \) -approximation schemebin-packing problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Recommendations

• An Efficient Approximation Scheme for Variable-Sized Bin Packing
• Bin packing with divisible item sizes
• Variable Sized Bin Packing
• Polynomiality for bin packing with a constant number of item types
• Polynomiality for Bin Packing with a Constant Number of Item Types

Cites work

• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Application of Bin-Packing to Multiprocessor Scheduling
• Bin packing with divisible item sizes
• Bin packing: Maximizing the number of pieces packed
• Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
• On a dual version of the one-dimensional bin packing problem
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(12)

• Closing the gap for makespan scheduling via sparsification techniques
• An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension
• Bin packing with controllable item sizes
• An APTAS for bin packing with clique-graph conflicts
• An Efficient Approximation Scheme for Variable-Sized Bin Packing
• New algorithmic results for bin packing and scheduling
• Bin packing with fixed number of bins revisited
• On minimizing the makespan when some jobs cannot be assigned on the same machine
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• Bin packing with divisible item sizes
• Relations between capacity utilization, minimal bin size and bin number
• Strip Packing vs. Bin Packing

This page was built for publication: Bin packing with restricted piece sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825652)