MBS' algorithm for One Dimensional Bin Packing Prblem (minimum bin slack)

Question

Am working on resolving the 1D bin packing problem, and as initial population, am going to start with the MBS' generator particles. I was looking on the net for the MBS' (minimum bin slack) algorithm and couldn't find it . please could someone help me ?

Answer 1

The MBS' is an improvement for the MBS (Minimum Bin Slack) heuristic which is based on the following steps :

• At each step, an attempt is made to find a set of items (packing) that fits the bin capacity as much as possible.
• In this sense, MBS is similar to Hoffmann’s algorithm for solving assembly line balancing problems.
• At each stage, a list I’ of n’ items not assigned to bins so far, sorted in the decreasing order of sizes is kept.
• Each time a packing is determined, the items involved are placed in a bin and removed from I’, preserving the sort order.
• The process begins with I’= I and it ends when the list I’ becomes empty.
• Each packing is determined in a search procedure that tests all possible subsets of items on the list I’ which maximally fit the capacity of bin.
• The subset that leaves the least slack is adopted; If the algorithm finds a subset that fills the bin up completely, the search is stopped, and there is no better packing possible in this state.
• The search is started from items of greater size, i.e., from the beginning of I’ because items of relatively big sizes are usually harder to pack in bins and, therefore, an attempt to pack them first should be undertaken.

[MBS Algorithm] http://i.stack.imgur.com/jUltR.png

MBS' :

• It's identical to MBS except that it uses an initialisation procedure that speeds up the algorithm.
• The following modification to MBS is proposed: before the one-packing search procedure is invoked, an item (the seed) is chosen and permanently fixed in the packing.
• This can be done because every item must be placed in a bin anyway.
• A good choice of seed is the item of the greatest size, i.e., the first on the list Z’.
• This will leave the least space in the bin to fill during the search, thereby shortening the time of processing.
• Moreover, the solution process will be forced to use larger, and for that reason more trouble-causing, items first.