Scheduling of industrial processes

With the increasing need to manufacture items in specialized factories (regardless of the industry), the demand for specially designed management systems has rapidly grown.These systems must, irrespective of the company’s size in question, help the user plan work so that all orders are completed within the required time, and the overall equipment efficiency is thoroughly monitored and improved.

For a tiny enterprise, production can be planned with great precision using only simple tools, so the user requires optimal solutions from a dedicated system. For a large factory with a few dozen or production lines, with orders counting in the hundreds every day, a certain margin of error is acceptable since the object of interest is to optimize a not easily solvable problem for a human. For both types of users, the responsibility of such a system is exceptionally important as the plan should be created in a few seconds so as not to discourage the use of the software. In addition, if the waiting time for the plan was too long, it may turn out that in the meantime, new orders were accepted and the plan would become outdated before it was created. In this article I will describe one of the ways to approach the problem so that the result of the scheduling is satisfactory for both small and large scale enterprises.

The problem described here is based on the well-known job shop scheduling problem. It is an optimization problem in which we have a set of machines and jobs consisting of an ordered sequence of operations. The execution time of each task on a given machine is known, so we need to find the start time and assigned device of each operation so that the whole production ends as fast as possible. It is crucial that the order of operations is maintained and two tasks are not performed simultaneously on the same machine.

The presented task of finding an appropriate sequence of tasks is only a theoretical basis for real-world problems. Let’s have a deeper look into the issue of printing children’s books as an example. Several different operations are performed for the finished product to reach the warehouse The pages of the book are printed. Some of these pages may have additional embellishments. Often several pages are printed on a single sheet of paper, so the sheet has to be cut to separate them. Regardless of this process, a cover is created and then combined with the printed content of the book. Finally, the whole product is appropriately packaged.

As we can see, some of the operations occur in succession, others, such as the creation of the cover and the printing of the content, can be done in parallel, and some, such as the embellishments, are optional. In addition, not all the material is available in the plant, which creates additional logistical constraints. Looking more holistically, orders also have deadlines, making other scheduling constraints.

We already know what industrial scheduling is, but what effect does increasing the number of requirements have on a potential scheduler? Both complexity and task size are among the major factors affecting the time it takes to create a production schedule. So let’s take a closer look at the relationship between tasks and the time needed to solve them.

I have already mentioned that the main determinant of the time an algorithm will spend on processing is the complexity of the task (relationships between operations and additional constraints) and the size of the problem (for example with children’s books, it is the number of different orders and the number of available machines). Let us look at how the problem would be solved using the Integer Linear Programming (ILP) algorithm to understand better why that is.

ILP is used to optimize problems that can be written using a set of inequalities (constraints) and returns the optimal solution by minimizing the objective function. For example, for the problem of finding a rectangle with the smallest area for which the sum of the sides must be greater than 10 and no side can be smaller than 1, we would create 3 equations. Suppose we call the sides of the rectangle a and b respectively, then:

The goal function would be then to minimize the factor of a and b.

Equations, variables, objective functions, but how does it relate to the problem of scheduling? Let’s start with what are the unknowns we are looking for. To create a plan, we need to know when each operation should be started (because we know how long the operation takes and on which machines it can be performed). The equations will therefore limit the possible solutions. For example, the operation of cutting paper has to be performed after printing the text on it can be written as:

But what’s our objective function then? Various strategies can be adopted, although the simplest way to achieve a good plan is to minimize the total production time. Therefore, our objective function is to minimise the completion time of the last production.

A problem instance thus defined can be passed to a specialized solver. The number of unknowns depends largely on the number of tasks, and the number of equations is also related to the number of constraints resulting from the complexity of our task.

The question is whether the increase in time at a certain point becomes unacceptable. As we can see in picture 2, for the next 50 test tasks, the rise in time for the algorithm providing an exact solution is exponential, so that the computation time from minutes quickly turns into hours and then days. So what can we do to find a solution for such large tasks?

Heuristic algorithms are characterized by much higher time efficiency and are often chosen for large tasks. The difficulty associated with them is the appropriate choice of parameters so that the result is as close as possible to the optimal result. An example of a heuristic algorithm for scheduling is Dispatch Rules (DR). It is based on creating an empty plan and then choosing iteratively one task and placing it at the plan. It is so simple that you could plan production on a piece of paper! So, where is the complexity involved? The problem is the strategy of choosing the right task in each step to get the best result. To select the best operation in a given step, we need a rule to perform the selection, like choosing the shortest task. Is a single rule sufficient? What if multiple tasks are “the best”? The way to deal with this problem is to create an ordered set of rules, such that if there is more than one best task according to a given rule, further rules are applied to a subset of the previously selected tasks until exactly one task is selected.

Let’s see how such a list could look like:

This way, we achieve our plan quickly. The question is how quickly compared to the same tasks we saw in Figure 2? The answer can be seen in Figure 3. But where is the red color from dispatch rules processing time? The best part is that it’s so fast that it takes only a few seconds, even for big tasks!

But what is the difference between the obtained plan duration? Let’s use a bigger set of 150 productions and see Figure 4. We can clearly see that DR from a specific problem size tends to get significantly worse results.

If we create a metric from combined values of the algorithm’s plan duration and execution time, we can see how good the given algorithm is. The results can be seen in Figure 5. We can clearly see that for small tasks ILP is better, then both algorithms tend to have similar results, and then Dispatch Rules are clearly better for large problems. But we wanted one method for all problems? So what can we do now?

The answer is to use both algorithms! How? We will create a decision-making module to choose a proper algorithm for a given scheduling problem. The decision will be taken based on problem characteristics. The number of operations, jobs, machines, and a number of constraints will be used to assess which method best suits the case.

A decision module (using decision trees) trained on 150 training examples has obtained an accuracy of approximately 90 percent on a 50-element test set. What does this result mean? For 90 percent of the cases, the best result was chosen from two possible, but it does not mean that this result is incorrect for the rest of the cases. The plan created for 10 percent of the issues was worse by at most 20 percent compared to the better solution. These cases occurred in a space where the difference between the results was insignificant.

As a result, we have a scheduler built from two methods, which can handle the selection of the better algorithm with great accuracy. Its additional advantage is the possibility of adding more methods if necessary. A planning software containing such a comprehensive tool will therefore give the user a high-quality production plan in a timeframe that does not discourage them from using the software!

Related posts:

As the world is moving at a fast pace and as 2020 is almost at the end. The covid -19 has shown all of us how fragile the world is. A microscopic virus has put us on our knees and has left us fragile…

Lock and door opening tools can help you gain access to your home or office without a key. These tools mimic the operation of a key by fishing under the lock’s lever handle. Levers that have a…

Within the last year or so, the crypto space has seen tremendous growth. Every day an article can be found touting the analysis from another enterprise or economic mogul weighing in on the debate; is…