A stochastic variable size bin packing problem with time constraints

Research output: Book/ReportReportAcademic

859 Downloads (Pure)


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

Publication series

NameBETA publicatie : working papers
ISSN (Print)1386-9213


Dive into the research topics of 'A stochastic variable size bin packing problem with time constraints'. Together they form a unique fingerprint.

Cite this