Buying a new machine? What about optimal planning?

Diagram 1: Colour Wheel

The dilemma

Companies invest heavily in new machines with which they want to increase the production capacity of the facility. If we were able to find a way to make work processes smarter, we would not only produce our product faster but also increase our working capacity without the need to purchase expensive new machines.

Work planning is an important part of the work processes at a production facility.

Effective planning of work is crucial for the timely delivery of orders, the allocation of materials and labor, and ultimately the optimization of profits. However, it turns out that work planning is a demanding process, with many different options, and that requirements also change rapidly in production facilities. In this article, we will present a system that introduced a key change for one of our customers - a manufacturing company, one which optimized their planning process and brought about a significant effect on revenue. The company is engaged in the printing of various products, and therefore, ink is one of their main materials. Before the project, we reviewed their work process and found that a bottleneck was exactly planning the work process. We implemented a system that monitors production on all machines in real-time, visualizes and communicates the current status of each machine, and calculates the optimal order of work tasks.

In the work order database, we are given a set of work tasks where each one has different elements. Depending on the properties of successive work orders, one order is carried out faster than another. Let's look at the example of cleaning the ink-filled firing chambers. If we insert a blue color into the chamber and wish to use an orange color in the same chamber in the next iteration, we will spend more time cleaning the chamber than if we first printed the task with a green color, as the green color is a mixture of blue and yellow, while orange is a blend of yellow and red.

In this simple case, we can see the possibility of changing colors in one firing chamber.

Things become interesting when we try to plan work tasks with three to eight colors on three machines with 6 firing chambers, each working at a different speed and only one possessing the technology for printing a certain type of printed matter. We choose between more than 200 different shades of colors. The most important thing being - for every work task we must keep in mind the promised delivery deadline and ensure that this is not missed.

We have already mentioned many parameters that we need to be careful about and coordinate accordingly. As there is a large number of combinations, we would need a lot of time (it would be practically impossible) to calculate each one manually. The time complexity of the problem with 3 machines is n!3^n. As an interesting fact: if we had 42 orders, there are as many different possible order combinations as there are atoms on Earth; in the case of 59 orders, this number is equal to the number of all atoms in the Universe. Problems of such rank are in computer science called NP full problems. This means that it is very difficult to search for all the possible solutions and find the best one because there are simply too many options, even on the computer. If you had to find all the possible orders for 190 work tasks, you would have to inspect more than 190!

Since manufacturing is an ever-evolving process, it constantly changes.

 A work order is made, printed, the product is created, so it is not considered for planning anymore. On the other hand, new work orders are constantly getting ordered and all of which have to be assigned in the current plan. That's why we need a system that will refresh plan in real-time with new work tasks. We need a method that will be able to find a better order at any moment if one work order is removed or added to it. We can look at the plan as to the living, ever-changing organism. Darwin said that the survival of a species does not depend on its power, nor its intelligence, but its ability to respond to change. We view one solution of the plan as a subject in a line. Multiple individuals can be compared to each other so that in a given population we choose the one best suited to solve the problem. However, due to the changing process, the best individual of the population will not always be the same and will change frequently. Darwin's inspired method, called the genetic algorithm, is therefore used.

The genetic algorithm explained.

To help us understand how the algorithm works, imagine that we want to create the best football team of eleven people in the world. Let's say we have a way to measure the quality of the team when all 11 players are playing. This is called a fitness function and it returns a certain score. 

The function consists of various aspects to capture the assessment of the game in defense and attack, the price of football players, measures personal connections between them, then weighs all these attributes and provides a number that represents a score.

Because there are too many options and too many people in the world, we only have limited options to evaluate different teams, so we must use different methods of changing players. In the first round, we draw up a few teams and rank them according to our fitness function. In the next round, we want to create new teams and keep some of the old ones in order to find the team with the best score. Of course, some of the best-ranked teams are included in the next round (this method is known as 'elitism'). We take any two teams and we exchange some of the players to get two new teams. We call this the crossover method, and it grants the possibility of some players feeling better in another team. The method is repeated several times. It sometimes happens that we simply cannot find a better team with the presented methods, thereby reaching the local optimum. That's when we use a mutation method that randomly finds one player in the world and changes them with a player in a team. It turns out that because of this method, the genetic algorithm "escapes" the local optimum and finds better results. After a few iterations, we get a very good team, but we can never know if it is the best. Eventually, players also become older, and there are new, younger players with different abilities coming in and we must therefore always evaluate, change teams and look for better team options.

Diagram 2: Local and global optimum. The Genetic algorithm searches the space and tries to come as close to the global optimum as possible

We used similar methods to find the best work order for the aforementioned company - one of our customers, but we replaced players with work tasks. Due to the changing nature of the problem, the algorithm constantly searches for the best solution and does so by using the described methods. It turns out that the algorithm finds a sufficiently good solution in only a few iterations, significantly reducing the time used in the production of the same number of working tasks, simply due to the more well- organized order of working tasks.

On each line, the production time was reduced by about 2 hours, resulting in the number of working Saturdays being significantly reduced.

The company also reduced the number of late orders.

Diagram 3: An example of a work order display

The red line illustrates the current time, the red square represents a work task that took too much time to be carried out, the dark blue color preceding the red line represents a task, carried out on time. The system tracks the task status with the current task blinking blue (if there is still time for the task to be finished) or red (if there is not). For the planned tasks (right from the red line) the displays show if previously required operations were completed.

This system enabled us to increase the capacity of production machines, allowing the company to produce more orders without additional purchases of new production facilities.

This created several hundred thousand euros of additional revenue, which represented a significant increase compared to the size of this production facility. With the implementation of state-of-the-art algorithms, we managed to show that it is possible to use knowledge from the academic sphere in small and medium-sized production plants and apply it to real-world problems. Not only are such problems solvable, but optimal solutions can also have a direct impact on profits and can be visible in a very short time.

Experience has shown that there is still plenty of room for improvement in many companies and that there are not enough pre-existing systems and algorithms being implemented and applied in everyday tasks and processes that people still do manually.

With this project, we actualized and optimized several processes in the production cycle and demonstrated the power with which science can help the industry.