Jan 30 2021
[The featured image is an ISOTYPE from Marie Neurath (1936)]
Maps of symbols connected by lines are the most common form of graphic communication about operations, next to bar charts, pie charts, and time series. The symbols may be a variety of pictograms and there may be different types of lines, including arrows, double-headed arrows with a variety of arrowheads, with dashed lines of varying thicknesses…
This is about what you can do with such maps beyond communicating, and the challenges of mapping systems that don’t fit on one slide. It is also about improving current practices.
- Maps in Manufacturing
- Graphs In Everyday Life
- Topographical Maps
- Graphs in Math, Applied Math, and IT
- Graph Theory
- Networks in OR
- The Vazsonyi procedure
- From PERT/CPM to Critical Chain
- Traveling Sales Reps, Milk Runs, and Equipment Changeovers
- Queueing Networks
- Graphs and Database Technology
- Further Reading
Maps in Manufacturing
In designing, improving, or communicating about manufacturing systems, besides plots of quantities, we use many kinds of maps. We use blueprints of facilities but also many other types. They can be VSMs, Process maps, Bills of Materials, Equipment Statecharts, Cause-and-effect diagrams, Mind maps, Product evolutionary trees, Systems diagrams, or Deming’s Production System Chart, … Click on any entry in the following gallery for examples of these and a few non-manufacturing charts:
These maps all convey different information, in ways that are more or less self-explanatory. They are all made of symbols connected by lines. Formally, The symbols may be a variety of pictograms and there may be different types of lines. You can attach text, photographs, or links to any symbol or line. Let’s explore what they have in common as a result of this formal structure, and the ways of working with them when their complexity is beyond what the human mind can grasp in a single picture.
Maps Of Systems
In some of these maps, the symbols represent parts or elements that together exhibit behavior or meaning that the individual constituents do not. The lines represent relationships and interactions between and among the parts. In other words, in INCOSE terms, these maps represent systems, and usually not in their entirety. Instead, the maps throw light on some of the interactions in the system and omit others. They are projections that make some features visible that details would bury in any attempt to represent the entire system. In other maps, the symbols are for discrete states a particular object goes through, and the lines represent the events that trigger transitions.
Complexity In Real Systems
With real systems, complexity quickly rises, and there are several ways to address it:
- Visualization. Starting with a few high-level aggregates, you drill down to lower levels as in a multi-level bill of materials taking you from an aircraft to a wing, engine mounts, and rivets… This results in a tree of linked maps that is easy for a reader to navigate but not for an author to generate.
- Automated mapping. Generating an accurate map of an existing system that is laden with undocumented workarounds is such a daunting task that Frederick Brooks called it the current physical tar pit. Defenders of the status quo often insist on it as a way to bog down change attempts. Strategically, an effective response is to do it on a subset of the operations that is small enough to visualize graphically and large enough to highlight the dysfunctions. Technically, if a system records all the actual transactions, process mining tools can automatically infer the actual processes.
- Validation. The maps are visualizations of human-generated master data and subject to errors, like manufacturing operations without any output, BOM items that go into themselves, or equipment states that you cannot transition out of,… When dealing with hundreds or thousands of items, you need software to flag such problems. This validates a map as well-formed but not the symbols’ values. It can detect whether a screw assembles onto itself but not whether the number of screws is 10 where you need 12.
- Calculations. Examples of calculations on the objects in maps include exploding finished goods demand into requirements for purchased materials, calculating the earliest completion time for a project, or sequencing products through a machine with setups. You can calculate this manually only on toy examples for teaching, that you can visualize.
- Simulations. Where calculations are insufficient or not feasible, we can use simulate the behavior of the systems that are mapped under a variety of circumstances, with graphic animations for small systems and without animation for large ones.
Same Maps For Different Problems
Sometimes, you can represent different problems by formally identical maps. For example, when mapping the activities of a traveling sales rep visiting customers in different cities, there is a symbol for each city and a line for each road between two cities. When mapping the setups of a production machine making multiple products, there is a symbol for each product and a line for the changeovers between two products. The problems of plotting a route for a sales rep and of sequencing products through a machine are then formally identical.
Graphs In Everyday Life
We now use graphs in everyday life without giving them a second thought but perhaps we should. The Shanghai Metro is a subway system with 17 lines, 358 stations, and a total route length of 453 mi. It serves 13 million riders/day, for a city of 24 million. It provides maps that summarize this entire network on a single page:
This map crudely approximates the topography of the city and does not show distances. In fact, the only information it conveys about stations is their connections and their organization in intersecting lines. The map is useful because of the details it omits.
One key question is whether it is connected: does the network offer a path between any two stations. In Shanghai, the loop line in the center makes it visually clear. In New York City, it is also true but not quite so obvious when you look at the map. Generally, if you have a network in the form of a list of nodes and branches, can you automatically determine whether it is connected? It is the sort of question that graph theory answers.
Rider Route Planning
The riders use the map to plot routes, and there is often more than one way to travel between two stations. What matters is how long it takes, not how many miles it covers. Subways usually take roughly equal times between consecutive stations and you can calculate the ride time from the number of stations. Then you need to pad it to include walking and waiting time at the start, at points of connections, and at the end, all of which vary with the time of day. Experienced city dwellers are usually adept at estimating these travel times.
The System Operator’s Perspective
Subway system operators view this map from a different perspective. The map as a whole represents the object of their work. In routine operations, they tweak the frequency and length of trains to match the demand by time of day or day of the week. Then, they also decide where to build new lines.
We should pay more attention to these maps as models of clear communication. They convey information about a complex system to millions of people, none of whom needs any training to read them. They have a clear purpose and are self-explanatory. It’s a benchmark worth considering.
This article is about graphs and networks, which is not the only way to map a system. While graphs highlight relationships between objects, topographical maps show relationships between objects and territory. They can also be used to find or share other information. The following map, for example, shows the geographical distribution of the factories in Germany for several industries:
While the factories for car assembly and milling machines are distributed throughout the country, the semiconductor factories are all near the western border and the aircraft plant along a North-South axis in the center. Why? It appears that defense considerations drove these location choices. The aircraft plants were built between the two World Wars, as far as possible from potential enemies in the East and West. The semiconductor plants were built during the Cold War, as far as possible from the Iron Curtain…
These maps were about a real territory but some draw them about an imaginary one. In their book on Lean Engineering, Cécile Roche and Luc Delamotte chose to show the subject as a territory with the following map drawn by Johanna Guillaume, which is reminiscent of Tolkien’s Middle-Earth and Martin’s Westeros.
Graphs in Math, Applied Math, and IT
For 300 years, mathematicians have had fun with graphs, coming up with clever insights that may or may not have practical applications. You can skip the section on graph theory unless you enjoy solving puzzles that require spatial thinking. Results are often proofs that a path exists or doesn’t exist but they are not about finding it. Sometimes, by serendipity, these results apply to real-life problems.
Graph Theorists On Real Problems
When called upon, graph theorists have worked on practical problems. W. T. Tutte, for example, cracked the Lorenz code that Hitler used to communicate with his top deputies. He doesn’t say whether it involved graph theory, to which he returned after the war. His fellow codebreaker Gordon Welchman used graphs to show how the Enigma machines encrypted and decrypted letters differently with every keystroke, based on its initial settings:
This example from a decoded message means that, on the 5th keystroke, an E was encoded into a P and, on the 8th, into an I. The edges are not arrows because they represent a pairing rather than a one-way assignment. To decrypt an Enigma message, you initialized the machine with the same settings as for encoding, typed in the coded message, and out came the plain text. If on the 5th keystroke, it turned an E into a P when you typed in the plain text, it also turned a P into an E when you typed in the encoded text. According to Welchman, these graphs influenced the design of the machines used to break the Enigma, the bombes that you can now see as a visitor in Bletchley Park:
Operations Research As Theory
Operations Research (OR), on the other hand, was born as an applied field. OR took graphs of vertices and edges and relabeled them networks of nodes and branches, through which flow quantities of interest. OR practitioners then produced algorithms to optimize these flows. It was about finding the one best way to put a network to use. Over decades, however, OR drifted away from practical applications and became a branch of math, with limited application to Manufacturing.
From yet another perspective, database technologists have also shown an interest in graphs, and graph databases are emerging as a challenge to the dominant technology of relational databases, from the 1970s. This has yet to affect Manufacturing in a major way.
In graph theory, a graph is a structure composed of vertices and edges that join pairs of vertices. In the geometry of graphs, all that matters is connectedness. It’s different from the geometry of angles, parallels, conic sections, and distances along straight lines, as in mechanical and civil engineering. In city life, you don’t go from A to B as the crow flies.
Instead, you follow the streets and the transportation system, and cross rivers where there are bridges or tunnels. It is navigating a graph, where connectedness and time matter more than mileage. In Shanghai, the path from Fuxing Park to the Science & Technology museum is not a straight line, whether you are driving or riding the subway:
The Bridges of Königsberg
In 1736, Leonhard Euler lived in Königsberg, now Kaliningrad. The city had 4 areas separated by water and connected by 7 bridges. Was it possible to visit every area by crossing each bridge exactly once? This puzzle kept the citizens entertained, and not finding solutions. By using a graph model of the problem, Euler proved it couldn’t be done, which started graph theory as a branch of math. The map of Königsberg and its bridges was as follows:
The topographical details were irrelevant to the problem and made it look more difficult than it really was. Euler made the key issues visible by reducing the map to the characteristics that mattered, as in the following picture:
Your walk through the city can start and end at any vertex, and you can visit the other vertices multiple times, as long as you use every bridge once and only once. As you can’t use the same bridge twice, every time you visit a vertex, you have to leave it on a different edge than the one you arrived on, and you can’t reuse either one on a later visit. Since you need a pair of different edges for every visit, the number of edges connected to every intermediate node must be even. At most two vertices, where you start and end, can be connected to an odd number of edges. Vertex A is connected to 5 edges; vertices B, C, and D, to 3 edges each. Therefore, there is no solution.
Following in Euler’s footsteps, mathematicians have applied this kind of reasoning to many other puzzles, few of which have solutions that are quite so easy to explain.
Three Houses and Three Utilities
When drawing a map of a graph, you try to avoid crossing lines because they make the maps difficult to read. Captions, in particular, can be easily confused as attached to the wrong edges. Here is an example from a document by Robin Kent that is an example of the confusion created by crossing lines:
Impossibility Of Avoiding Crossed Lines
In a result that is slightly more difficult to prove than the absence of a solution to the puzzle of the Bridges of Königsberg, graph theory tells us that it is impossible to connect three houses to three utilities in a plane without crossing lines.
It’s a question of counting loops. In a loop, you can remove an edge and keep the vertices connected. The maximum number of edges you can remove while keeping the whole graph connected tells you how many loops it contains.
When connecting three houses with three utilities, you have 6 vertices and 9 edges. Since you need at least 5 edges to connect 6 vertices, you can remove at most 4 edges and stay connected. In other words, you can have at most 4 loops.
Assume we have connected the three houses to three utilities without crossing lines. As seen in the picture the edges connecting any 2 utilities with the 3 houses form 2 quadrangular loops. The 3rd utility cannot be inside of any of these loops because lines would cross. Altogether, by symmetry, the 3 pairs of utilities with the 3 houses form 6 loops. Since you can’t have more than 4 loops with 6 vertices and 9 edges, it is impossible.
Workarounds To Avoid Crossing Lines
Graphically, you can finesse the issue in a variety of ways.
By feeding all utilities to a single additional vertex that you may call a manifold, and route a bundle of three utilities to each house. It does eliminate crossing lines on the map but it may mislead the reader if the manifold does not exist in reality.
Stack diagrams are another way to avoid a jumble of crossing arrows. They were first used for communication protocols, which led to “toaster models” for software apps and then to house diagrams for production systems. This is an example of a toaster model of manufacturing software systems:
The toaster slots are software functions that share data and services from a common platform and interact with users through a common interface. If you pull the layers apart, you expose a web of crossing connections, each one meaning that a module in one layer invokes another in the layer below.
In a similar vein, the Toyota Production System is frequently explained through a “TPS House” showing some features as the foundation for others. There are many versions posted on the web. This is the one from the Lean Enterprise Institute:
It is similar to the toaster model but not as consistent in the meaning of positions. Heijunka, for example, is presented as foundational to both Just-In-Time and Jidoka. Those who are familiar with it may not see why it would be a prerequisite to Jidoka.
Placing it in the foundation suggests that it should be implemented before the approaches it supports. It is, in fact, an advanced approach to production scheduling that unfamiliar managers struggle to understand. Perhaps, it belongs more in the Just-In-Time column than in the foundation.
Deliberate Crossing Lines
Sometimes, lines are artificially made to cross for artistic purposes, as in Charles Sheeler’s famous shot of crossing conveyors that didn’t exist at Ford’s River Rouge plant:
The artist wanted to make the reader admire the complexity of the plant, not understand its flows. Marketers often pursue the same objectives but managers and engineers, in principle, don’t, and do not take kindly to “symbol salad.” In 1992 Robert Schaffer wrote a paper in HBR excoriating activity-driven programs in companies, often described by unintelligible flow diagrams. He opened with the following cartoon:
From Euler To Poincaré
In Finite Element Analysis (FEA), you approximate a surface in a 3D space as a mesh of triangles to perform numerical calculations based on local approximations.
Such meshes are special cases of graphs, where the triangles are called faces. When used for numerical calculations, the triangles are flat with straight edges. As graphs, however, the triangles don’t have to be flat, the sides don’t have to be straight, and their lengths don’t matter. What makes a triangle here is just having 3 vertices and 3 edges, with each vertex connected by a single edge to each of the other two. The triangulation of surfaces in this sense has the astonishing property that:\chi = Number\,of\,Faces - Number\,of\,Edges + Number\,of\,Vertices
is invariant when you refine the mesh by splitting any large triangle into smaller ones or coarsen it by merging small triangles into bigger ones. It’s a result that is not simple to prove but fun to play with as we can see in a few simple examples.
From Tetra Paks To Cylinders
A simple shape like the original Tetra Pak can be viewed as made up of 4 triangles, its \chi = 4 - 6 + 4 = 2. If we subdivide each face into 4 smaller triangles, we find \chi = 12 - 22 + 12 = 2. We could keep subdividing and would always get the same \chi value.
If instead, of flat panes we have a flexible, elastic wire mesh, wrapped around a sphere, we can see that we can approximate the sphere as closely as we want as a mesh of small triangles, while retaining \chi = 2 , as in the following figure:
If the sphere is a ball of play-dough, we can give it a different shape by rolling or tapping it. As long as we don’t split it into multiple pieces or make a hole in it will still have \chi = 2 . On the other hand, if you split it into two balls, then the set of two balls will have \chi = 4 . If two surfaces have different \chi , they cannot be morphed into each other as described above. We can morph a sphere into a cylinder, and verify that the cylinder’s \chi = 8-12+6 = 2 . If, however, we make a ring from the cylinder by bending it like a slinky and joining its top to its bottom, we end up with a bagel shape that has \chi = 0 .
From Cylinders To Bagels
You remove the top and bottom faces, and merge 3 vertices and 3 edges from the top of the cylinder with their counterparts on the bottom. The difference in \chi is therefore \Delta \chi = -2 +3 -3 = -2 .
This \chi is called the Euler-Poincaré characteristic of the surface and it serves to group surfaces into classes.
Four colors suffice (1976)
Possibly the most famous result of mathematical graph theory is the four-color theorem, which says that four colors are enough in a map for no two adjacent regions to have the same color. In the graph model of a topographical map, the borders are the vertices and the regions the edges, as in the following example, where the Kentucky-Ohio and Kentucky-Tennessee borders are vertices, and Kentucky the colored edge that joins them.
In those terms, the theorem says that four colors are enough to assign colors to edges so that no two touching regions have the same color. Reducing a topographical map to a graph eliminates information that is irrelevant to the problem, like the size or shape of a region. This problem, however, is complex enough that it could not be solved manually. It required reviewing about 1,834 possible configurations, which Kenneth Appel and Wolfgang Haken did with the help of a computer program in 1976. Here is a four-color map of the states in the US:
The University of Illinois celebrated their achievement with a custom postmark. This pure math result found a practical application in mobile telephony. In 2015, Raaman Nair gave the following example:
“One of the 4 Color Theorem most notable applications is in mobile phone masts. These masts all cover certain areas with some overlap meaning that they can’t all transmit on the same frequency. A simple method of ensuring that no two masts that overlap have the same frequency is to give them all a different frequency. But, as the government owns all frequencies and charge for each, one wants to use the minimum possible number of frequencies. The areas covered can be drawn as a map and the different frequencies can be represented as colors.”
Networks in OR
In Operations Research (OR), also known as Management Science, vertices are called nodes, and edges branches, arcs, or links, and a graph with any kind of flow in its branches is called a network. While the mathematicians are concerned with structure and the existence of characteristics in graphs, OR is instead focused on algorithms to optimize some measure of network performance, like the volume of flow or traversal time. Of the many network algorithms that OR has produced, only a few come up in Manufacturing.
Often, even where an OR algorithm finds an optimum for small networks, the time it requires grows so fast with the numbers of nodes and branches that it can’t provide a timely answer. You cannot take all day to generate a production schedule for that day.
What constitutes a “small” network grows with IT over time, and many actual problems in Manufacturing are, in fact, small for 2021 IT. Some are not small but operations must go on, with or without OR, and practitioners use methods they call heuristics, that are not guaranteed to be optimal.
Heijunka, the Kanban system, and Bucket Brigades are all heuristics. The OR focus then shifts to estimating or bounding how close the heuristics come to the elusive optima. Much of Julien Bramel and David Simchi-Levi’s The Logic of Logistics is devoted to this topic.
Dieter Jungnickel’s Graphs, Networks and Algorithm (4th Edition) is a 2013 textbook that covers both the math of graph theory and network methods from OR. Network Models and Optimization, by Mitsuo Gen et al. (2008), is strictly about networks and focused on genetic algorithms.
When asked why all the academic presentations at the 2009 APIEMS conference were about Genetic Algorithms(GA) when it was a term I had never heard in factories, Prof. Gen’s answer was “It’s what you can get research grants for.” A 2020 paper by Adam Slowik and Halina Kwasnicka now presents GA as a mature subcategory of Evolutionary Algorithms.
The Vazsonyi procedure
The representation of Bills Of Materials (BOM) as networks and the calculations it enables are the contributions from OR’s network theory that I find most useful in Manufacturing. The main results are from Andrew Vazsonyi in the early 1950s and predate the coining of the term “BOM,” See The BOM Rap, with Part II on the Vazsonyi procedure and Part III on Scaling Up for details. There is no reference to his work in Hillier & Lieberman’s textbook Introduction to Operations Research, but Vazsonyi is wrongly forgotten because his methods for working with BOMs are both simple and clever.
ERP Is Not Enough
While likely buried in the codes of ERP systems, Vazsonyi’s methods are of interest to any engineers looking to analyze material and component consumption in more ways than they can with ERP systems. As math, the algorithms are limited to additions, multiplications, and inversions of matrices, for which you can invoke built-in functions in Excel or other packages. Regarding analytics from the corporate ERP system, a factory engineer in a multinational company recently shared his experience with me:
- The implementation of the system disrupted and made the flows more complex, particularly due to the supplier’s insistence that the physical flows be patterned after their system and not the other way around.
- The system itself consumes a lot of resources (Human and IT) and does not provide simple links with other systems. It takes from 4 minutes to half an hour to get any data out of it.
- By policy, extraction tools are reserved for IT staff. After discussion with many colleagues from other industries this limitation seems to be global. The tools, script, queries, … exist but with access limited to IT.
- Typical improvement requests follow the following scheme: (1) describe a practical problem, (2) translate it into technical problems, and (3) provide technical solutions, which will be translated into software. In our structure, Remote IT platforms require the user to directly propose technical solutions. The user does not necessarily know the details of how the ERP system works, and especially not the limitations of the modules the company purchased. The user also does not necessarily have the skills to describe and translate the problem into the required Unified Modeling Language (UML) format.
- Hosting the ERP system on a remote platform delays the response by months, depending on the priorities set by a person who often only knows the problem through the weak qualitative analysis made by the end-user.
Engineers Need The Vazsonyi Procedure
As a consequence, to do any work with the BOMs, rather than use the tools of the ERP system, this engineer, along with many others, prefers to extract the rawest possible data and perform his own analyses locally. For this purpose, tools like the Vazsonyi procedure come in handy. It implies that they should not be buried many levels deep in the ERP software but instead explicitly invoked by end-users.
From PERT/CPM to Critical Chain
As discussed in The Project Game, the main tool for project management is the old action item list. There is a variant in software development that they call “kanban,” with the action items on Post-It notes instead of a list and moved on a whiteboard between columns for “To Do,” “In-Process,” and “Done,” but the logic is the same and it has the same key shortcoming that precedence constraints do not appear. The 100-year old Gantt chart highlights the differences in scope and duration between tasks but also ignores precedence constraints.
Projects As Networks: PERT and CPM
In the late 1950s, Willard Fazar, Morgan Walker, and James Kelley started representing projects as networks with activities as nodes and precedence constraints as branches. 60 years later, this representation is their most useful legacy, albeit one to which the literature on project management devotes little attention.
The following is an example of a project network diagram from MS Project. The boxes are tasks and the arrows precedence constraints, mostly finish-to-start, but some as also finish-to-finish, meaning that both tasks must be completed at the same time. The pink bits are the critical path, explained below.
The writers focus on the use of this structure for planning, in two different ways:
- Fazar developed the Program Evaluation and Review Technique (PERT) now largely forgotten. It was based on probability distributions for task durations for which, usually, no data is available.
- Walker and Kelley developed the Critical Path Method (CPM) that is now ubiquitous in project planning software. It only requires one duration for each task and identifies the sequence of tasks with no slack, known as the critical path. These were the tasks for which any delay passes on to the entire project. Conversely, any reduction in duration for any of these tasks redounds to the entire project, at least until other tasks get on the critical path.
The Critical Path
If you work forward from start, considering precedence constraints, you find the earliest time a task can be completed; going backward from project completion, you find the latest completion time of a task. If the earliest and latest completion times are identical, the task is on the critical path.
The logic of CPM is unimpeachable; its translation to reality, not so much. It is a technical approach to a human problem. CPM bases its calculations on task durations that, particularly in innovative projects, no one can properly measure. The individual in charge wants this time long and the manager wants it short. They negotiate the value the system uses, and it has little to do with the time actually needed.
When a project manager shows a team the critical path, it affects behaviors. Some members in charge of tasks that are not on the critical path. They shift their priorities elsewhere and don’t work on these tasks until they make it onto the critical path. This isn’t how the textbooks say CPM works.
Critical Chain Project Management
Eli Goldratt introduced Critical Chain Project Management (CCPM) in 1997. Rather than padding each task duration in anticipation of contingencies, he pads the entire project. You generate a plan with no allowance for delays on any task but build in slack for the project completion time, as a budget on which each task draws as needed. The project manager monitors the consumption of this budget to make it last just enough to finish on time.
Goldratt compares this to planning a trip to the airport. If the streets and roads are empty, the airport is 30 minutes away. You expect, however, that there will be delays and allow 70 minutes for the trip instead of 30. This allowance is for the trip as a whole, not for any traffic light, freeway on-ramp, or construction site. You don’t know ahead of time where you will consume the slack but you know that you have budgeted enough to make your flight.
While PERT, CPM, and CCPM are generic approaches applicable to any project, several other methods have been developed for specific applications:
- In construction, Last Planner System (LPS) from Glenn Ballard and Greg Howell, aims to engage multiple layers of subcontractors in collaborating to improve performance. Unlike higher-level planners, the “Last Planner” interacts directly with the workers who erect I-beams, pour concrete, or lay cables.
- In construction also, Adam Frandson’s Takt Time Planning breaks construction tasks into modules of the same duration that teams can execute in parallel.
- In maintenance, yearly shutdowns occasion massive inspections and repairs in chemical or power plants. Sometimes, shutdown/restart cycles the equipment through a series of phases that control maintenance access to various components. In a nuclear reactor, for example, the water level in the primary circuit goes up and down as part of a refueling outage, making some equipment accessible. This series of phases then is the skeleton around which you organize the maintenance tasks. This skeleton formally looks like a critical path but isn’t one. Tasks are part of it because they enable or disable other tasks, not because they have no slack.
Network methods developed as part of OR have had an impact on project planning and management, albeit not nearly as dramatic as the developers expected. See Engwall (2012) for a retrospective on the project PERT was developed for, after 50 years.
Traveling Sales Reps, Milk Runs, and Equipment Changeovers
A sales rep based in Boston, MA, needs to visit customers in Framingham, Worcester, Palmer, Webster, Putnam, CT, Woonsocket, RI, Providence, RI, and Brockton, MA. According to Google Maps, the route covers 247 miles in 5 hr 13 minutes, and it has tolls.
The Traveling Sales rep Problem (TSP) is finding the route that is shortest, fastest, or cheapest. The customers are the nodes and the roads are the branches. The solutions vary depending on the time of day, the day of the week, the season, and traffic. Given all the required data, there is always a solution. Among all the possible permutations, there is at least one sequence with the lowest mileage, travel time, or cost. For decades, OR has been developing better ways of finding it than brute-force enumeration of all permutations.
Milk-runs And The TSP
A manufacturing plant doesn’t have sales reps visiting customers. If, however, it uses milk runs, each truck visits a set of about 5 suppliers within 35 miles. For the suppliers’ sake, you do not change the sequence every day.
If you have, say 50 suppliers within range, first you break them down into 10 groups of ~5. If all deliveries go to a single Receiving area, then you base the groupings on the supplier locations; otherwise, you consider the Receiving destination within the plant.
Clustering suppliers rarely takes more than pinning them on the map. This is because their small factories tend in industrial zones on the outskirts of towns. Few suppliers locate their plants miles away from services and utilities.
The truck travels most of the distance from the customer plant to the cluster of suppliers. The distances within the cluster are short, or it’s not a cluster. This gives limited value to seeking an optimal sequence. If you operate a milk-run to suppliers that are not close to one another, it is a tiny TSP. A brute-force enumeration of all routes will give you the best one in a split second on any office laptop.
Machine Changeovers And The TSP
Formally, changing over a machine from product X to product Y is like driving from city X to city Y, with the changeover procedure playing the role of the route.
The possibly asymmetric matrix of changeover times is like the mileage chart between cities with one-way roads, so that the travel times from X to Y and Y to X may be different. You can model machine changeovers as the TSP. The questions are (1) whether you need to optimize product sequencing, and (2) if you do, by what methods.
Unless a factory has undertaken a setup time reduction effort (SMED), it generally has no good data on changeover times. Most ERP systems don’t even support setup matrices. Instead, each product-operation has fields for a single setup time, as if the prior condition made no difference. There is no point in applying sophisticated algorithms to this kind of data.
Post-SMED on a given machine, all setup times are short. Before SMED, a matrix of good changeover times is not available. After SMED, you have engineered the problem out of existence. It doesn’t leave much room for a TSP algorithm to make itself useful.
Why Bring Up TSP?
So why bring it up? Because, in every plant, there is an engineer asking endless hypothetical “what if” questions. Presenting a toy case does the job of fobbing them off without offending them.
Theoretically, the asymmetric matrix of changeover times is not even the most complex case. In a machining center, for example, the tools to load for the next product depend on the complete production history. Once you have reengineered the process to make all products use a common tooling package, this problem also goes away.
If the quantities through a network are discrete, arrive and leave randomly at each node, it is a queuing network. They can be workpieces, passengers, data packets, or any other entities. Queueing networks have had more applications to service, transportation, and communication networks than to Manufacturing.
Closed Queueing Networks
If the number inside the network is capped, you have a closed queueing network. You don’t allow a new unit to enter until another one leaves. In Manufacturing, any approach that caps the WIP is a special case of a closed queueing network. This includes the Kanban system but the descriptions of the Kanban system do not refer to that theory.
Their only use of queueing theory is in the formulas for calculating the number of Kanbans in a loop. It’s based on Little’s Law, which is usually not even acknowledged. Little’s Law relates the steady-state means of throughput, inventory, and lead times in operations. It applies to a network by treating it like a single server. Then it applies as well as to any node within that network.
The only other result from queueing theory that is widely cited in Manufacturing is Kingman’s Formula, about system saturation. With very few restrictions, it says that, when a single-server queue saturates, its waiting time grows like the inverse of the server’s Availability = 1-Utilization. If it’s 98% busy, its waiting time will be twice as long as if it were 96% busy. It is, however, about a single-server, not a network.
It is more often used qualitatively than quantitatively. You use it to explain the explosive growth of waiting time when you saturate your equipment. You don’t use it to estimate these waiting times.
Discrete-event simulators of production work off a network model that is supposed to be a digital twin of an actual factory. The simulators don’t generate ideas but they help you evaluate ideas you already have. Large-scale simulations take considerable skills and effort to set up. Their use is limited to operations that are too complex to grasp in other ways.
Many produce animations, that humans can review to assess how realistic they are. Simulating 100 years of use, on the other hand, is better done without animation, and you then summarize the simulated history into a variety of performance metrics.
There are many uses for small-scale simulations that an engineer can set up quickly without expensive tools. The formula for the number of Kanbans in a loop, for example, includes an arbitrary safety factor. So it’s not really that “scientific.”
You can improve on it by setting up a simulation of the Kanban loop. You feed it the actual consumption of the output for the past 6 months and choose a number of Kanbans. Then you observe how much WIP stays in the loop and how frequently shortages occur. See pp. 211-213 in Lean Logistics.
Graphs and Database Technology
Manufacturing professionals usually know little about the database structures that hold their data in enterprise systems. When they want to analyze data, they extract tables from these systems into Excel. As discussed in Excel Hell, it is dysfunctional but so common that practitioners are not even aware of alternatives.
The relational database model created in 1970 provided access to tables, selecting columns, joining tables by matching values in columns, and filtering rows. Even for an end-user, it is simpler than overlaying tables on a spreadsheet grid. In particular, does not expose you to the risk of leaving out the last 5 rows when dragging a cursor. The technology took about 20 years to mature but the relational model is still the standard in 2021. Relational Database Management Systems (DBMS) dominate the market and most enterprise systems rely on them.
The Graph Database Concept
Limitations of the relational model appeared over time. The software industry came up with various alternatives or enhancements. A recent one was graph databases, which organize data in graphs, with vertices and edges, in the graph theory sense.
Application To Master Data Management
The domain of application of graph databases that may be of most interest in Manufacturing is Master Data Management (MDM). Master Data is the data that changes only as a result of a management decision. It includes the revisions of products and processes, the equipment list, and the roster of human resources.
The Management of Master Data is its maintenance as rules change, companies merge, and systems are upgraded or replaced. Other applications include connections between members in social networks and recommendation systems.
Many bubble-and-arrows charts in manufacturing slideware are vague and ambiguous. It works in marketing because viewers project their desires on the material and assume that the product/service will meet them. Different members of the same organization will make different assumptions, that come to light when they start to use it.
Clarity, Precision, and Accuracy In Technical Communication
In technical communication, vagueness and ambiguity are the enemies. The map of the Shanghai subway has none. Most of it is self-explanatory, and there is a legend box at the bottom left for anything that isn’t. It’s a benchmark to keep in mind.
When brainstorming on a whiteboard, it’s OK to be loose. On the other hand, when presenting or training, we should be able to explain every graphic element. You should, for example, label operations consistently with imperative verb phrases, like “Drill side holes,” or “Pay invoice”; machines, with a descriptive name, as specific as appropriate; people, by their job functions.
Edges, too, can have many different meanings, which you should make clear. On a subway map, it is the existence of railroad tracks between stations. It is obvious and requires no explanation. In a VSM, it can be a flow of materials or information.
The two must look different. Each connection must be labeled as needed for the reader to understand exactly what it is that flows. Secondarily, it may also indicate the means by which it is flow. It may be trucks, ships, or airplanes for materials, versus XML messages or cards for data.
When connections represent precedence constraints, part-to-assembly relationships, or reporting relationships, it also must be made clear.
More Stringent Requirements For Models Driving Operations
The requirements are even more stringent when you use detailed models to drive operations by directing operators, machines, or suppliers.
Most real systems that you can model as networks are too complex to fit on one slide or page. This includes a supply chain with 250 Tier-1 suppliers, a fabrication process of 500 operations, or a BOM with 50,000 items.
There is value in aggregating objects into summaries that you can chart on a single page or slide. With nodes like “Engine Assembly,” “Final Assembly,” or “Painting,” you can show an entire car assembly process on one page; with nodes like “Fuselage,” “Wing,” or “Engine,” the bill of materials of an aircraft.
In each case, you must then be able to explode these nodes into lower-level networks, which may have common nodes. And you need to maintain these relationships to reflect changes. This is Master Data Management (MDM).
- Roche, C. & Delamotte, L. (2018) Lean en Ingéniérie Guide de Voyage (Lean in Engineering Travel Guide), L’Harmattan, ISBN: 978-2-343-14249-4
- Shpakovsky, N. (2016) Tree of Technology Evolution, CreateSpace Independent Publishing Platform, ISBN: 978-1539892182
- Robinson, I et al. (2013) Graph Databases, O’Reilly, ISBN: 978-1-449-35626-2
- Jungnickel, D. (2013) Graphs, Networks and Algorithms, Springer, ISBN: 978-3642322778
- Engwall, M. (2012) PERT, Polaris, and the realities of project execution, International Journal of Managing Projects in Business 5(4), September 2012 DOI: 10.1108/17538371211268898
- Gen, M., Cheng, R. & Lin, L. (2008) Network Models and Optimization, Multiobjective Genetic Algorithm Approach, Springer, ISBN: 978-1-84800-180-0
- Degani, A. (2001) Taming HAL, Palgrave, ISBN: 0-312-29574-X
- Hillier, F.S. & Lieberman, G.J. (2001) Introduction to Operations Research, 7th Edition, McGraw Hill, ISBN: 0072321695
- Tutte, W.T. (1998) Graph Theory as I have known it, Oxford University Press, ISBN: 978-0-19-966055-1
- Welchman, G. (1997) The Hut 6 Story, M&M Baldwin, ISBN: 978-0-947712-34-1
- Schaffer, R. H. & Thomson, H.A. (1992) Successful Change Programs Begin with Results, Harvard Business Review