The production scheduling problem

Production scheduling is a frequent and sensitive operational decision. Therefore, it is necessary to ensure that it is done effectively and efficiently on an ongoing basis. A wrong decision may not have a serious impact, but if the production schedules are not consistently adequate, this will end up deteriorating the profitability of the company.

The challenge

In general, when we talk about scheduling we mean detailed information regarding how production will be carried out. Depending on the context in question, obtaining a program consists of answering questions over the programming horizon such as the following. What production orders to launch? When does each order begin to be processed in each production center? In particular, on what station within that center? Who do I need to assign each operation? When will the preparation and cleaning operations take place?

The answer to the previous questions must comply with all the technical and business restrictions of the plant: intermediate product storage capacity, availability of raw material, delivery dates, availability of personnel …

The problem is extremely complex. If we had 100 production orders and 5 work centres, it would be necessary to decide for every two production orders, which one would be scheduled first in each center. In other words 22,750 “conflicts” would need to be resolved, either explicitly or implicitly.

There are features that can make the problem even more complex. Sequence-dependent change times are a good example of this. In a painting process, moving from a light colour to a dark one requires a much shorter sprayer cleaning time than going from dark to light. Likewise, keeping the same colour for a longer time will result in less unproductive time dedicated to cleaning but, in return, as the production series are longer, we can end up with a surplus of finished product in one colour and shortage in others.

When it comes to how to assess the quality of a program, there are different aspects that may be relevant and potentially conflictuous. For example, as I open more production centres and have more capacity, I will get the finished product sooner and I will be able to respond to delivery commitments, but in return, the cost will be higher. Ideally, we would like to translate all of this into a single KPI, preferably euros, but this is not always possible.

The traditional approach

On many more occasions than would be desirable, the way to approach this problem is through an expert with knowledge of the system who, through spreadsheets and the application of rules that simplify the problem is able to put on top of the table a schedule. This requires a significant fraction of his time, both to obtain an initial schedule and to introduce the necessary changes when some type of incident requires it.

The implications of this approach are varied and undesirable. On the one hand, despite the expert’s knowledge, the programs obtained are often far from optimal. This is a leak of money that can go unnoticed or camouflaged (an excessively high level of inventories can allow you to fulfill customers and not lead to any red lights, but at an unnecessarily high cost).

Due to its time-intensive nature, the reaction time to incidents such as urgent orders or breakdowns tends to be reduced and, depending on the incident, the impact can be much more than that of a leak. Furthermore, this slow process makes it difficult to explore the impact of different schedules on the relevant KPIs.

Lastly, there is a more subtle but not least downside, and that is the fact that one of the best connoisseurs of the system is dedicated to slowly and tediously composing next week’s schedule. In other words, the expert is solving puzzles instead of exploring new improvements to the system.

Let’s imagine a station that requires a specific and rare operator profile and it can only be used during one single shift every day. The scheduler will take this rule into account when creating a program. However, what would be the impact of hiring more operators matching that profile to operate the equipment in any shift? What’s more, how many operators should be hired? Would that be profitable? The time required for this analysis exceeds the time available to a scheduler, which leaves questions unattended or poorly addressed. This means lost opportunities for savings.

The solution: prescriptive analytics

As you can see, the scheduling problem can be too complex to reach an optimal solution through the use of traditional techniques or the knowledge of a human expert. The alternative is prescriptive analytics. Combinatorial problems such as scheduling are a natural field of application for this branch of mathematics.

Prescriptive analytics is based on the construction of mathematical models that, through equations, allow the solutions to the problem to be represented. For example, if we have two sequential commands i and j, either one or the other is scheduled first. It is possible to define a variable xij that equals one if i is programmed before j. Since i cannot be scheduled before j and, at the same time, j before i and, at the same time, one goes before the other, it must be true that xij + xji = 1.

In the same way, all the rules that must be respected can be formulated mathematically and delegate on specific software the resolution of all the equations needed to find the optimum.

There are alternative and more elaborate approaches that combine mathematical models, heuristics, metaheuristics, machine learning… The field is vast and has been extensively studied. Proof of this is a simple search in Google Scholar for the term “scheduling” that yields 3.8 million entries at the time of publication of this post.

Each company has its own puzzle. Scheduling can refer to job-shop systems or flow-shop systems; for systems that work on request or for stock; with the possibility of breaking the production of an order on consecutive days; with alternative routes for the products; with different stations that can do the same operation with different costs and times; there may be limited intermediate product storage capacity or, in practice, infinite.

In this context and with so many sources of complexity, analytics offers enormous advantages. For starters, it offers the optimal or near-optimal solution in a very short time. In other words, it offers better solutions and takes much less time than the expert analyst This is so because it explores the solutions space “intelligently” while keeping a global view. Following the puzzle analogy, it keeps all pieces in sight at the same time.

This eliminates analyst bias, or at least it makes it explicit because tools can be developed that take into account different objectives, each with a different weight. Thus, it is possible to bet on less costly schedules yet with little slack in terms of personnel or, on the contrary, it is possible to bet on schedules that allow a more homogeneous work distribution even when this may be more expensive or may leave more room for the fulfillment of the delivery dates.

The analyst can compare alternatives, fix part of the schedule, make changes to what the tool proposes… In short, he has a “very powerful calculator” at the service of better decision-making.

Finally, and very importantly, the user can explore alternative system configurations, such as increasing the number of stations in parallel for a given job or purchasing a second machine, managing to evaluate its impact on production, income and, finally, the ROI of such investments.

In order to get the most out of prescriptive analytics in the case of scheduling, each case needs its specific treatment, which allows to consider its singularities effectively and efficiently. Only in very elementary cases is it possible to adapt a generic tool to the case in question.


Every time a mediocre production schedule is generated and we do not resort to prescriptive analytics, we give up the possibility of obtaining savings and its accrued effect can be as expensive as it is difficult to fix.

The good news is that the undelying math is the same. It “only” takes knowledge of the art and rigour to develop analytical models that respond to the particularities of each case.

Leave a Reply