<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> <title>Frepple / Cluster and level algorithm</title> <link rel='stylesheet' href='../styles.css' type='text/css' /> <!--PageHeaderFmt--> </head> <body> <div id="container"> <div id="menubar"> <div id="logo" align="center"> <br/><img src='../frepple.bmp' alt="frepple" /><br/> <a href='http://www.frepple.com/'> <strong>a Free<br/>Production Planning<br/>Library</strong> </a></div> <div id="menu"> <br/> <h3><a href='../Main/HomePage.html'>Main</a></h3> <h3><a href='../UI/Main.html'>User Manual</a></h3> <h3><a href='../Tutorial/Main.html'>Tutorial</a></h3> <h3><a href='Main.html'>Reference Manual</a></h3> <h3><a href='../Main/FAQ.html'>FAQ</a></h3> <h3><a href='../reference/index.html'>C++ API</a></h3> <br/><div> </div> </div> </div> <div id="content"> <br/> <!--PageText--> <div id='wikitext'> <p><a class='wikilink' href='../Main/HomePage.html'>Main</a> > <span class='wikitrail'><a class='wikilink' href='Main.html'>Reference Manual</a> > <a class='wikilink' href='Solver.html'>Solver algorithm</a> > <a class='selflink' href='Solvercluster.html'>Cluster and level algorithm</a></span> </p> <p class='vspace'>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. </p> <p class='vspace'>A <strong>cluster</strong> 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.<br />Internally, each cluster is represented by a number.<br />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. </p> <p class='vspace'>Material flows in the network have a direction. This creates a sense of direction in our network which is expressed by the <strong>level</strong> concept.<br />An operation consumes and produces material, as defined by the flow entities (aka bill of material or recipe).<br />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.<br />Raw materials have the highest level number. </p> <p class='vspace'>The level and cluster number are helpful for the various solver algorithms. They provide valuable information about the structure of the network. </p> <div class='vspace'></div><div><img src='../uploads/Frepple/clusters_and_levels.jpg' alt='' title='' /></div> <p class='vspace'>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. </p> <p class='vspace'>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. </p> <p class='vspace'>Note: An updated algorithm has been designed for the cluster computation. Its advantage compared to the current implementation is a much better effiency in the case of frequent model updates. The computation will be completely incremental, compared to the single pass for all entities in the current implementation. </p> <p class='vspace'>The detailed flow of the algorithm is as follows: </p> <div class='vspace'></div><div style='font-style: italic;' > <p>// Initialisation<br />Lock the function<br />Reset the level and cluster to -1 on all resources, operations and buffers<br />Reset the total number of clusters </p> <p class='vspace'>// Main loop<br />Loop through all operations </p><div class='indent'>If the operation has no producing flow <div class='indent'>Activate the level computation </div></div><div class='indent'>If the operation isn't part of a cluster yet <div class='indent'>Activate the cluster computation </div><div class='indent'>Increment the cluster counter </div></div><div class='indent'>If both cluster and level computation are inactive, move on to the next operation </div><div class='indent'>Push the current operation on the recursion stack, with level 0 or -1 </div><div class='indent'>Loop until the stack is empty <div class='indent'>Pop an operation from the recursion stack </div><div class='indent'>Pop the value of cur_level from the stack </div><div class='indent'>Loop through the sub operations and super operations <div class='indent'>If their level is less than the current level <div class='indent'>Push sub operation on the stack, with the same level as the current operation </div><div class='indent'>Set the level and cluster fields </div></div><div class='indent'>Else if cluster is not set yet <div class='indent'>Push sub operation on the stack, with -1 as the level </div><div class='indent'>Set the cluster field </div></div></div><div class='indent'>Loop through all loadplans of the operation <div class='indent'>If level search is active and the resource level is less than the level of the current operation <div class='indent'>Update the level of the resource </div></div><div class='indent'>If the cluster of the resource is not set yet <div class='indent'>Set the cluster of the resource </div><div class='indent'>Loop through all operations that are loading the resource <div class='indent'>If operation cluster isn't set yet <dl><dd><div class='indent'>Push the operation on the stack, level -1 </div><div class='indent'>Set the cluster of the operation </div></dd></dl></div></div></div></div><div class='indent'>Loop through all flows of the current operation <div class='indent'>If this is a consuming flow and level_search is active and the level of the buffer is less than the current level +1 <div class='indent'>Level recursion is required </div></div><div class='indent'>If level recursion is required or the cluster of the buffer is not set yet <div class='indent'>Set the cluster of the buffer </div><div class='indent'>Loop through all flows connected to the buffer <div class='indent'>If it is a consuming flow and level search recursion was enabled <div class='vspace'></div><div class='indent'>todo incomplete documentation </div></div></div></div></div></div><p class='vspace'>// Catch buffers missed by the main loop<br />Loop through all buffers which don't have any flow at all. </p><div class='indent'>Increment the total number of clusters </div><div class='indent'>Set the cluster number to the new cluster </div><p class='vspace'>// Catch resources missed by the main loop<br />Loop through all resources which don't have any load at all. </p><div class='indent'>Increment the total number of clusters </div><div class='indent'>Set the cluster number to the new cluster </div><p class='vspace'>// Finalization<br />Unlock the function </p></div> </div> <!--PageFooterFmt--> <!--HTMLFooter--> </div></div> </body> </html>
