Bin packing problem (guided)

Collaboration Bin_packing_problem

Given a set of items, each having a specifed size, and a set of bins each having a specified capacity, the Bin packing problem can be described as the problem of finding the minimal number of bins required to include all items such that the total size of all items associated to a bin does not exceed the capacity of the bin.

The model contains guidance on the allocation of items to bins.

Diagram

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Items" name="items" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="ItemRequests" name="item_requests := 0" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="Bins" name="bins" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="AvailableBins" name="available_bins := 0" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="ItemsIncluded" name="items_included := 0" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="Blocker" name="blocker := false" type="boolean">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

Process ItemProcess

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Timestamp" name="timestamp" type="decimal">
            </bpmnos:attribute>
            <bpmnos:attribute id="Size" name="size" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
    </bpmnos:status>
</bpmn2:extensionElements>

DataObject DataObject_1xt50y3

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Instance" name="instance" type="string">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

Task RequestActivity

<bpmn2:extensionElements>
    <bpmnos:messages>
        <bpmnos:message name="Request">
            <bpmnos:content attribute="instance" key="Item">
            </bpmnos:content>
            <bpmnos:content attribute="size" key="Size">
            </bpmnos:content>
        </bpmnos:message>
    </bpmnos:messages>
    <bpmnos:status>
        <bpmnos:operators>
            <bpmnos:operator expression="item_requests += 1" id="Operator_0pjma63">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Process BinProcess

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Timestamp" name="timestamp" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
        <bpmnos:restrictions>
            <bpmnos:restriction expression="total_size <= capacity" id="Restriction_3br81vk">
            </bpmnos:restriction>
        </bpmnos:restrictions>
    </bpmnos:status>
</bpmn2:extensionElements>

DataObject DataObject_2xt50y3

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Instance" name="instance" type="string">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

DataObject DataObject_1pee096

<bpmn2:extensionElements>
    <bpmnos:attributes>
        <bpmnos:attribute id="Capacity" name="capacity" type="decimal">
        </bpmnos:attribute>
        <bpmnos:attribute id="TotalSize" name="total_size := 0" type="decimal">
        </bpmnos:attribute>
        <bpmnos:attribute id="Used" name="used := false" objective="minimize" type="boolean" weight="1">
        </bpmnos:attribute>
    </bpmnos:attributes>
</bpmn2:extensionElements>

Task WaitActivity

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:restrictions>
            <bpmnos:restriction expression="items_included == items" id="Restriction_339o4h3" scope="exit">
            </bpmnos:restriction>
        </bpmnos:restrictions>
        <bpmnos:operators>
            <bpmnos:operator expression="available_bins += 1" id="Operator_0oi8qea">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Event-SubProcess EventSubProcess

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:attributes>
            <bpmnos:attribute id="Item" name="item" type="string">
            </bpmnos:attribute>
            <bpmnos:attribute id="Size" name="size" type="decimal">
            </bpmnos:attribute>
        </bpmnos:attributes>
        <bpmnos:restrictions>
            <bpmnos:restriction expression="blocker == false" id="RestrictionBlocker" scope="entry">
            </bpmnos:restriction>
        </bpmnos:restrictions>
        <bpmnos:operators>
            <bpmnos:operator expression="blocker := true" id="OperatorBlocker">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Ad-hoc SubProcess AdHocSubProcess

<bpmn2:extensionElements>
    <bpmnos:status>
    </bpmnos:status>
</bpmn2:extensionElements>

Task IncludeItemActivity

<bpmn2:extensionElements>
    <bpmnos:status>
        <bpmnos:operators>
            <bpmnos:operator expression="used := true" id="OperatorUsed">
            </bpmnos:operator>
            <bpmnos:operator expression="total_size += size" id="OperatorTotalSize">
            </bpmnos:operator>
            <bpmnos:operator expression="items_included += 1" id="OperatorItemsIncluded">
            </bpmnos:operator>
            <bpmnos:operator expression="blocker := false" id="OperatorUnblock">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Event CatchRequestMessage

The guidance for the allocation of items to bins requires that all items have sent their request, all bins are available, and that the inclusion of an item will not exceed the capacity. Allocations are made in an order that the item which minimise the residual capacity is chosen first.

<bpmn2:extensionElements>
    <bpmnos:message name="Request">
        <bpmnos:content attribute="item" key="Item">
        </bpmnos:content>
        <bpmnos:content attribute="size" key="Size">
        </bpmnos:content>
    </bpmnos:message>
    <bpmnos:guidance type="message">
        <bpmnos:attributes>
            <bpmnos:attribute id="Residual" name="residual" objective="minimize" type="decimal" weight="1">
            </bpmnos:attribute>
        </bpmnos:attributes>
        <bpmnos:restrictions>
            <bpmnos:restriction expression="item_requests == items" id="Restriction_0ve1mi3" scope="exit">
            </bpmnos:restriction>
            <bpmnos:restriction expression="available_bins == bins" id="Restriction_247eq94" scope="exit">
            </bpmnos:restriction>
            <bpmnos:restriction expression="total_size + size <= capacity" id="RestrictionSize" scope="exit">
            </bpmnos:restriction>
            <bpmnos:restriction expression="blocker == false" id="RestrictionBlocker">
            </bpmnos:restriction>
        </bpmnos:restrictions>
        <bpmnos:operators>
            <bpmnos:operator expression="residual := capacity - total_size - size" id="Operator_2oajb1v" type="decimal">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:guidance>
</bpmn2:extensionElements>