Bin packing problem

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="Bins" name="bins" type="integer">
        </bpmnos:attribute>
        <bpmnos:attribute id="ItemsIncluded" name="items_included := 0" type="integer">
        </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: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: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:operators>
            <bpmnos:operator expression="total_size += size" id="Operator_096714o">
            </bpmnos:operator>
            <bpmnos:operator expression="used := true" id="Operator_2bo3f0c">
            </bpmnos:operator>
            <bpmnos:operator expression="items_included += 1" id="Operator_3cjc7m2">
            </bpmnos:operator>
        </bpmnos:operators>
    </bpmnos:status>
</bpmn2:extensionElements>

Event CatchRequestMessage

<bpmn2:extensionElements>
    <bpmnos:message name="Request">
        <bpmnos:content attribute="item" key="Item">
        </bpmnos:content>
        <bpmnos:content attribute="size" key="Size">
        </bpmnos:content>
    </bpmnos:message>
</bpmn2:extensionElements>