frePPLeOpen source Production Planning
  • Home
  • Documentation
  • C++ API

Cluster and level algorithm

Resources, operations and buffers are connected with each other with loads and flows. An operation has a collection of loads and flows. Each flow establishes a connection with a buffer, and each load a connection with a resources. The entities thus constitute a network graph. In this network context we define clusters and level as follows.

A cluster is a set of connected entities. When a network path across loads and flows exists between 2 entities they belong to the same cluster. When no such path exists they are effectively situated in independent sub-networks and clusters.
Internally, each cluster is represented by a number.
Clusters allow us to group entities and are very useful in multithreaded environment: since the clusters are completely independent we can use different threads to solve each cluster as a separate subproblem.

Material flows in the network have a direction. This creates a sense of direction in our network which is expressed by the level concept.
An operation consumes and produces material, as defined by the flow entities (aka bill of material or recipe).
In this context the level is a number that is defined such that the level of a consumed material buffer is always higher than the level of the produced material buffer. The demand is normally (but not exclusively!) placed on the material buffers with level 0, and the level number increases as we recurse through the different levels in the bill of material.
Raw materials have the highest level number.

The level and cluster number are helpful for the various solver algorithms. They provide valuable information about the structure of the network.

The algorithm used to compute the level and cluster information is based on a walk through the network: We select an unmarked operation and recurse through the loads and flows to find all connected entities, updating the cluster and level information as we progress.

For efficiency, the algorithm is implemented as a lazy function, i.e. the information is only computed when the user is retrieving the value of a level or cluster field. The algorithm is not incremental (yet), but computes the information for the complete network in a single pass: a change to a single entity will trigger re-computation of all level and cluster information for all entities.

The pseudo-code of the algorithm is as follows:

// Initialisation
Lock the function
Reset the level and cluster to -1 on all resources, operations and buffers
Reset the total number of clusters

// Main loop
Loop through all operations

  // Check the operation
  If the operation has no producing flow
    Activate the level computation
  If the operation isn’t part of a cluster yet
    Activate the cluster computation
    Increment the cluster counter
  If both cluster and level computation are inactive, move on to the next operation

  // Recursively process the operation stack
  Push the current operation on the recursion stack, with level 0 or -1
  Loop until the stack is empty
    Pop an operation from the recursion stack
    Pop the value of cur_level from the stack

    // Detect loops in the network structure
    If the operation was already visited in the recursion loop
      Move on to the next operation

    Loop through the sub operations and super operations
      If their level is less than the current level
        Push sub operation on the stack, with the same level as the current operation
        Set the level and cluster fields
      Else if cluster is not set yet
        Push sub operation on the stack, with -1 as the level
        Set the cluster field

    Loop through all loads of the operation
      If level search is active and the resource level is less than the level of the current operation
        Update the level of the resource
      If the cluster of the resource is not set yet
        Set the cluster of the resource
        Loop through all operations that are loading the resource
          If operation cluster isn’t set yet
            Push the operation on the stack, level -1
            Set the cluster of the operation

    Loop through all flows of the current operation
      If this is a consuming flow and level_search is active and the buffer’s level is less than the current level +1
        Level recursion is required
      If level recursion is required or the cluster of the buffer is not set yet
        Set the cluster of the buffer
        Loop through all flows connected to the buffer
          If it is a consuming flow and level search recursion was enabled
            If operation level < level + 1
            else if operation cluster isn’t set yet
              Push the operation on the stack, level -1
          Set the buffer level to level + 1
          else if operation cluster is not set yet
            Push the operation on the stack, level -1
            Set the cluster of the operation

// Catch buffers missed by the main loop
Loop through all buffers which don’t have any flow at all.
  Increment the total number of clusters
  Set the cluster number to the new cluster

// Catch resources missed by the main loop
Loop through all resources which don’t have any load at all.
  Increment the total number of clusters
  Set the cluster number to the new cluster

// Finalization
Unlock the function

    • Getting started
      • 1 – Introduction
      • 2 – Installation
      • 3 – Entering data
      • 4 – Modelling concepts
      • 5 – Your first model
      • 6 – Your first plan
    • Modeling guide
      • Simplified domain model
      • Detailed domain model
      • Environment variables
      • Python interpreter
      • Global parameters
      • Buffer
      • Calendar
      • Customer
      • Demand
      • Flow
      • Item
      • Load
      • Location
      • Operation
      • Suboperation
      • Operationplan
      • Problem
      • Resource
      • SetupMatrix
      • Skill
      • Resource skill
      • Solver
    • User guide
      • Supported browsers
      • Getting around
        • Logging in
        • Logging out
        • Changing password
        • Navigation
          • Menu bar
          • Jump search
          • Context menus
        • Filtering data
        • Sorting data
        • Selecting time buckets
        • Exporting data
        • Importing data
        • Customizing a screen
        • User preferences
        • User permissions and roles
        • Comments
        • History – Audit trail
      • Data maintenance screens
      • Supply Path / Where Used
      • Plan analysis screens
        • Problem report
        • Constraint report
        • Inventory report
        • Inventory detail report
        • Resource report
        • Resource Gantt report
        • Resource detail report
        • Operation report
        • Operation detail report
        • Demand report
        • Demand detail report
        • Demand Gantt report
        • Forecast report
        • Performance indicator report
      • Execution screen
      • Batch commands
        • frepplectl
        • frepple
        • freppleservice.exe (Windows only)
    • Installation guide
      • Windows installer
      • Compiling on Windows
      • Linux binary packages
      • Compiling on Linux
      • Compiling from the source code repository
      • Running the VMWare virtual machine
      • Other platforms
      • Configuring multiple models in the user interface
      • Configuring as a Python extension module
    • Extension modules
      • Forecast module
      • Order quoting module
      • REST web service module
      • OpenERP connector module
      • Linear programming solver module
    • Technical guide
      • Architecture
      • Source code repository
      • User interface
        • Creating an extension app
        • Translating the user interface
        • Adding or customizing a report
        • Style guide
      • Solver engine
        • Code structure
        • Class diagram
        • Planning algorithm
          • Top level loop
          • Demand solver
          • Buffer solver
          • Flow solver
          • Load solver
          • Operation solver
          • Resource solver
        • Cluster and level algorithm
        • Extension modules
        • Style guide
        • Portability
      • Security
      • Unit tests
        • buffer_procure_1
        • calendar
        • callback
        • cluster
        • constraints_combined_1
        • constraints_combined_2
        • constraints_leadtime_1
        • constraints_material_1
        • constraints_material_2
        • constraints_material_3
        • constraints_material_4
        • constraints_resource_1
        • constraints_resource_2
        • constraints_resource_3
        • constraints_resource_4
        • constraints_resource_5
        • datetime
        • deletion
        • demand_policy
        • flow_alternate_1
        • flow_alternate_2
        • flow_effective
        • forecast_1
        • forecast_2
        • forecast_3
        • forecast_4
        • forecast_5
        • forecast_6
        • jobshop
        • load_alternate
        • load_effective
        • lpsolver_1
        • multithreading
        • name
        • operation_alternate
        • operation_available
        • operation_effective
        • operation_pre_post
        • operation_routing
        • pegging
        • problems
        • python_1
        • python_2
        • python_3
        • safety_stock
        • sample_module
        • scalability_1
        • scalability_2
        • scalability_3
        • setup_1
        • setup_2
        • skill
        • xml
        • xml_remote
    • FAQ
    • License
      • GNU Affero General Public License
      • GNU Free Documentation License
    • Third party add-ons
  • Copyright © 2010-2013 frePPLe bvba