A Stochastic Variable Size Bin Packing Problem with Time Constraints

S. Fazi, T. Woensel van, J.C. Fransoo

Research output: Working paperOther research output


In this paper, we extend the classical Variable Size Bin Packing Problem (VS-BPP) by adding time features to both bins and items. Speciffically, the bins act as machines that process the assigned batch of items with a fixed processing time. Hence, the items are available for processing at given times and are penalized for tardiness. Within this extension we also consider a stochastic variant, where the arrival times of the items have a discrete probability distribution. To solve these models, we build a Markov Chain Monte Carlo (MCMC) heuristic. We provide numerical tests to show the different decision making processes when time constraints and stochasticity are added to VSBPP instances. The results show that these new models entail safer and higher cost solutions. We also compare the performance of the MCMC heuristic and an industrial solver to show the effciency and the effcacy of our method.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages28
Publication statusPublished - 2012
Externally publishedYes

Publication series

NameBETA Working Paper Series


Dive into the research topics of 'A Stochastic Variable Size Bin Packing Problem with Time Constraints'. Together they form a unique fingerprint.

Cite this