A Stochastic Model of Bin-Packing

Recent research in combinatorial bin-packing models is extended to a stochastic model in which an arbitrary distribution of piece sizes is assumed. The asymptotic expected bin occupancy is obtained for a simple on-line algorithm. Convergence properties are also presented so that, for a given set of pieces, this measure can be related to the expected number of bins required relative to an optimization rule.

• Publication year

  1980

• Venue

  Information and Control

• Publication date

  1980-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0019-9958(80)90050-9
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Performance of Heuristic Bin Packing Algorithms with Segments of Random Length

  1977cited by this paper
• Sufficient conditions for ergodicity and recurrence of Markov chains on a general state space

  1975cited by this paper
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

  1974cited by this paper
• Fast Algorithms for Bin Packing

  1974cited by this paper
• Probability theory

  1963cited by this paper

• An In-depth Study of LLM Contributions to the Bin Packing Problem

  2025cites this paper
• Lower Bounds for Several Standard Bin Packing Algorithms in the Random Order Model

  2025cites this paper
• Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-constrained Optimization Approach

  2022cites this paper
• Near-optimal Algorithms for Stochastic Online Bin Packing

  2022cites this paper
• New strategy to improve the dotted board model for solving two dimensional cutting and packing problems

  2021cites this paper
• An introduction to stochastic bin packing-based server consolidation with conflicts

  2021cites this paper
• A Classification Framework for Time Stamp Stochastic Assignment Problems

  2020cites this paper
• Online Adaptive Bin Packing with Overflow

  2020cites this paper
• Optimal Control of Production and Maintenance Operations in Smart Custom Manufacturing Systems with Multiple Machines

  2019cites this paper
• Joint production and maintenance operations in smart custom-manufacturing systems

  2019influential citation
• New Results on the Probabilistic Analysis of Online Bin Packing and its Variants

  2019cites this paper
• Overcommitment in Cloud Services: Bin Packing with Chance Constraints

  2019cites this paper
• A Stochastic Bin Packing Approach for Server Consolidation with Conflicts

  2019cites this paper
• Algorithms for load balancing in electricity markets and data centers

  2018cites this paper
• High Availability for VM Placement and a Stochastic Model for Multiple Knapsack

  2017influential citation
• Overcommitment in Cloud Services Bin packing with Chance Constraints

  2017cites this paper
• Scheduling Under Uncertainty: Applications to Aviation, Healthcare and Aerospace

  2017cites this paper
• Evaluating the quality of online optimization algorithms by discrete event simulation

  2016cites this paper
• All-Around Near-Optimal Solutions for the Online Bin Packing Problem

  2015cites this paper
• Simplified Modeling and Solving of Logistics Optimization Problems

  2014cites this paper
• Online Optimization with Lookahead

  2014cites this paper
• On-line algorithms for bin-covering problems with known item distributions

  2014cites this paper
• Alternative Approaches for Analysis of Bin Packing and List Update Problems

  2014cites this paper
• An All-Around Near-Optimal Solution for the Classic Bin Packing Problem

  2014cites this paper
• Configuring Cloud Admission Policies under Dynamic Demand

  2013cites this paper
• Stochastic combinatorial optimization via poisson approximation

  2012cites this paper
• Bin Packing Problem with Uncertain Volumes and Capacities

  2012influential citation
• Asymptotic Methods in the Probabilistic Analysis of Packing and Partitioning Algorithms

  2011cites this paper
• Probabilistic alternatives for competitive analysis

  2011cites this paper
• Bin-packing Algorithms for Periodic Task Scheduling

  2010cites this paper
• Online Optimization: Probabilistic Analysis and Algorithm Engineering

  2010cites this paper
• An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling

  2009cites this paper
• Dynamic resource allocation for DVB‐RCS networks

  2008cites this paper
• A 0-1 KNAPSACK PROBLEM CONSIDERING RANDOMNESS OF FUTURE RETURNS AND FLEXIBLE GOALS OF AVAILABLE BUDGET AND TOTAL RETURN

  2008cites this paper
• Random-order bin packing

  2008cites this paper
• Probability maximization model of 0–1 knapsack problem with random fuzzy variables

  2008cites this paper
• Average Case Analysis of Bounded Space Bin Packing Algorithms

  2007cites this paper
• A Classification Scheme for Bin Packing Theory

  2007cites this paper
• A Bounded Item Bin Packing Problem over Discrete Distribution

  2006cites this paper
• A new average case analysis for completion time scheduling

  2006cites this paper
• Average performance analysis

  2006cites this paper
• Allocation of QoS Connections in MF-TDMA

  2005cites this paper
• Average-Case Performance Analysis of a 2D Strip Packing Algorithm—NFDH

  2005cites this paper
• The Impact of Fixed-size Frame on Bandwidth Utility Ratio

  2005cites this paper
• Allocation of QoS connections in MF-TDMA satellite systems: a two-phase approach

  2005cites this paper
• Average performance of greedy heuristics for the integer knapsack problem

  2004cites this paper
• Performance Analysis and Improvement for Some Linear On-Line Bin-Packing Algorithms

  2002cites this paper
• Packet scheduling with fragmentation

  2002cites this paper
• A new average case analysis for completion time scheduling

  2002cites this paper
• Deep performance analysis of Refined Harmonic bin packing algorithm

  2002cites this paper
• Approximate solutions to bin packing problems

  2002cites this paper
• Algorithms for the Relaxed Online Bin-Packing Model

  2000cites this paper
• Efficient resource allocation for QoS channels in MF-TDMA satellite systems

  2000cites this paper
• Discrete Online and Real-Time Optimization

  1998cites this paper
• Packing rectangles in a strip

  1997influential citation
• On-line Packing and Covering Problems

  1996cites this paper
• Randomized algorithms for the on-line minimum matching problem on euclidean space

  1995cites this paper
• Packings in two dimensions: Asymptotic average-case analysis of algorithms

  1993cites this paper
• Probabilistic Analysis of Packing and Related Partitioning Problems

  1993cites this paper
• Markov chains, computer proofs, and average-case analysis of best fit bin packing

  1993cites this paper
• A parallel stochastic optimization algorithm for solving 2D bin packing problems

  1993cites this paper
• Stochastic analysis of a slotted FIFO communication channel

  1993cites this paper
• A Probabilistic Analysis of Tour Partitioning Heuristics for the Capacitated Vehicle Routing Problem with Unsplit Demands

  1993cites this paper
• Stochastic analysis of a slotted communication channel

  1992cites this paper
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography

  1992cites this paper
• Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study

  1991cites this paper
• Stochastic Analysis of a Slotted FIFO Communication Channel: Constant and Uniform Message Lengths

  1991cites this paper
• How to pack better than best fit: tight bounds for average-case online bin packing

  1991cites this paper
• Bounded Space On-Line Bin Packing: Best Is Better than First

  1991influential citation
• Average-case analysis of the Modified Harmonic algorithm

  1989cites this paper
• Average-Case Analysis of the Smart Next Fit Algorithm

  1989cites this paper
• Martingale Inequalities, Interpolation and NP-Complete Problems

  1989cites this paper
• Next-fit bin packing with random piece sizes

  1989cites this paper
• Optimal Bin Packing with Items of Random Sizes

  1988cites this paper
• A packet multiplexing scheme for slotted broadband networks

  1988cites this paper
• Efficient transport of narrowband and broadband information units in ATM networks

  1988cites this paper
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

  1988cites this paper
• Martingale Inequalities and NP-Complete Problems

  1987cites this paper
• Probabilistic Analysis of Algorithms

  1987cites this paper
• Average-Case Analysis of the Modified Marmonic Algorithm

  1986cites this paper
• A Stochastic Analysis of the NFD Bin-Packing Algorithm

  1986cites this paper
• On the Expected Relative Performance of List Scheduling

  1985cites this paper
• Convergence of optimal stochastic bin packing

  1985cites this paper
• The average-case analysis of some on-line algorithms for bin packing

  1984cites this paper
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors

  1984cites this paper
• Some unexpected expected behavior results for bin packing

  1984cites this paper
• On a Dual Version of the One-Dimensional Bin Packing Problem

  1984cites this paper
• Probabilistic behaviour of optical bin-packing solutions

  1984cites this paper
• Approximation Algorithms for Bin-Packing — An Updated Survey

  1984cites this paper
• Probabilistic Analysis of Bin Packing Heuristics

  1984cites this paper
• A Probabilistic Analysis of the Next-Fit Bin Packing Algorithm

  1984cites this paper
• Bin packing with items uniformly distributed over intervals [a,b]

  1983cites this paper
• An Introduction to Proof Techniques for Bin-Packing Approximation Algorithms

  1982cites this paper
• Probabilistic Analysis of the LPT Processor Scheduling Heuristic

  1982cites this paper
• Models and Problems of Dynamic Memory Allocation

  1982cites this paper
• An average-case analysis of bin packing with uniformly distributed item sizes

  1982cites this paper
• A class of simple stochastic online bin packing algorithms

  1982cites this paper
• Probabilistic analysis of some bin-packing problems

  1982cites this paper
• Algorithms with Random Input

  1981cites this paper
• Probabilistic Analysis for Simple One- and Two-Dimensional Bin Packing Algorithms

  1980cites this paper