Maximizing the number of mixed packages subject to variety constraints

Maximizing the number of mixed packages subject to variety constraints

0.00 Avg rating0 Votes
Article ID: iaor20001904
Country: United Kingdom
Volume: 26
Issue: 13
Start Page Number: 1323
End Page Number: 1333
Publication Date: Nov 1999
Journal: Computers and Operations Research
Authors: ,
Keywords: bin packing, greeting cards, printing
Abstract:

We develop a polynomial-time algorithm to optimise a variant of the one-dimensional bin-packing problem with side constraints. We also develop a pseudo-polynomial procedure to actually implement that optimal solution. The specific application is the allocation of excess of a population of various types of cards (e.g., left over from a previous selling season) to fixed-sized ‘variety packs’ which guarantee a given level of variety (i.e., no more than k of any type of card). Some card types with large numbers (perhaps the most unpopular from the previous season) may have to be discarded to preserve the variety constraint. The method developed employs a test for feasibility of a given number of packs and includes a simple allocation procedure. A numerical example is provided along with (worst-case) complexity calculations. In addition, we solve a practical problem in which an organisation marketing Christmas cards sought to determine the impact of pack size and variety level on the level of unallocated cards.

Reviews

Required fields are marked *. Your email address will not be published.