gobblin.util.binpacking

Class WorstFitDecreasingBinPacking

java.lang.Object

gobblin.util.binpacking.WorstFitDecreasingBinPacking

All Implemented Interfaces:

WorkUnitBinPacker

public class WorstFitDecreasingBinPacking
extends Object
implements WorkUnitBinPacker

Implements a bin packing algorithm similar to worst-fit decreasing bin packing. Given a input list of WorkUnits, a WorkUnitWeighter function, and a maximum weight per MultiWorkUnit, packs the input work units into MultiWorkUnits.

The algorithm is as follows: * Sort work units decreasing by weight. * Compute the minimum number of MultiWorkUnits needed, and create them. * For each work unit, find the MultiWorkUnit with the largest space available, if it fits, add it there, otherwise, create a new MultiWorkUnit and add the work unit there.

Field Summary

Fields

Modifier and Type	Field and Description
static String	TOTAL_MULTI_WORK_UNIT_WEIGHT

Constructor Summary

Constructors

Constructor and Description
WorstFitDecreasingBinPacking()

Method Summary

Modifier and Type	Method and Description
List<WorkUnit>	pack(List<WorkUnit> workUnitsIn, WorkUnitWeighter weighter)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

TOTAL_MULTI_WORK_UNIT_WEIGHT

public static final String TOTAL_MULTI_WORK_UNIT_WEIGHT

See Also:

Constant Field Values

Constructor Detail

WorstFitDecreasingBinPacking

public WorstFitDecreasingBinPacking()

Method Detail

pack

@OverridingMethodsMustInvokeSuper
public List<WorkUnit> pack(List<WorkUnit> workUnitsIn,
                                                             WorkUnitWeighter weighter)

Specified by:

pack in interface WorkUnitBinPacker