Imagine you’re packing a suitcase for an airplane trip. There are many items that you would like to pack in the suitcase, but only some of them will fit and meet the airline’s weight requirements for luggage. How can you pack the suitcase to maximize the number of items you bring on your trip, the total weight of those items, and the combined value of the items?
This packing scenario is a real-world version of the Knapsack Problem, a classic problem in combinatorial optimization. In the Knapsack Problem, we’re given a knapsack that must be filled with objects that will fit within the physical confines of the knapsack and maximize the total possible value of the knapsack. Consider how you would solve this simple version of the Knapsack Problem:
A knapsack can hold a total of 80 units. There are six objects to choose from to put into the knapsack. The objects’ weights range from 15 to 40 units, and their values range from $22 to $40. In this version, there are 64 possible solutions, but only one that delivers the highest dollar value within the knapsack’s physical limitations.
With some trial and error, humans can eventually arrive at the best possible solution: using the white star, yellow pentagon, and blue triangle, which weigh a total of 77 pounds and offer a combined value of $99.
Where Manufacturers Encounter the Knapsack Problem
The Knapsack Problem is not only an issue for overpacking travelers – it’s also a problem that manufacturers deal with regularly. Facilities in today’s manufacturing environment are often incredibly complex, dealing with many constraints while trying to generate the most output and value from their total capacity. According to a 1999 study from Stony Brook University, the knapsack problem was one of the three most pressing combinatorial problems, and it’s only become more pressing as manufacturing processes have become more complex.
In real-world manufacturing processes, there can be hundreds of thousands of possible “objects” to fit into the facility’s production schedule. There are also various restraints, including raw material specifications, industry regulations, and the throughput capability of each individual machine. As a result, there are a near-infinite number of production schedules to choose from. With such a high degree of complexity, it’s logistically impossible for humans to consistently manually identify the schedule that will maximize their total output and value.
Using a Digital Twin to Solve the Knapsack Problem
In recent years, more manufacturers have turned to digital twin technology to help them solve their daily knapsack problems with increased efficiency and accuracy. A digital twin first creates a virtual, faithful copy of the site to properly represent the facility’s many activities and constraints. Then, the software uses a sophisticated algorithm to quickly run many sample production schedules, scan the possible combinations, and find an ideal solution that maximizes the value of the available resources.
Using a digital twin to perform this detailed scenario analysis can be incredibly advantageous for manufacturers. It helps ensure optimized resource allocation, recommending the best usage of each material and minimizing waste. It conserves team members’ time and effort, freeing up the hours of time they would’ve otherwise used solving these complex problems. While it may take a human days or weeks to solve just one manufacturing knapsack problem, it takes digital twin software just minutes. And, true to its core mission, the digital twin ensures the most value is generated from each production run, maximizing the dollar amount of each “knapsack.” APCI experts estimate that using a schedule based on the digital twin’s identified solution can result in 5-15% more throughput on average.
It’s important to remember that in reality, manufacturing circumstances will change often. Raw material shipments get delayed, and consumer demand changes often. That means without much notice, the facility’s “knapsack” may suddenly have fewer possible objects to fit in, or the value of each object may change. When conditions change, a digital twin can complete a new analysis for the revised knapsack very quickly, allowing the plant to minimize waste and begin operations based on the most up-to-date schedule.
In our 30+ years of experience working with many of the leading pharmaceutical companies, we’ve learned even world-class manufacturers with incredibly complicated processes can benefit from a digital twin. Each time the digital twin re-sorts processes to maximize throughput value or increase efficiency, the company has another opportunity to increase profitability. Hear how one of the world’s largest pharmaceutical companies has used VirtECS digital twin technology to successfully fit new products into their existing plant (or knapsack!) in this 2023 BioProcess International Conference keynote address.
