< back

Scheduling is a NP-Hard problem

September 29, 2014

Scheduling is a NP-Hard problem

Most conglomerate organizations of the modern world operate in a unique and unforeseen environment. Decisions have become more fact-based and analysis oriented, innovation and constant quantum improvement (process & product) is the key to mere survival. Also, management leadership relies heavily on data collected from multiple avenues far and beyond their physical reach, to provide future direction to these complex hugely interconnected social and economical bodies, stretching across all physical and economical boundaries. What make this environment unique, is the fact that the ability to harness high quality data to manipulate it and to apply the information thus generated for profits has improved drastically, which is an unforeseen change and is shaping the way industries of the world will exist in the future.

For organizations which manufacture products, the modern IT applications available are now capable of providing the decision makers with every instance of meaningful information, which is generated in their most modern and highly automated plants. This happens in real time and in visual form (graphs, pictures, videos) to enable better, faster more accurate decision making. But, it is important for manufacturers of this modern era to fully understand both the capability and constraints of these IT applications. As well as to make wise decisions where their process is concerned, since although the general perception about IT in manufacturing has changed and software has become a key part in the strategy mix for almost every manufacturer, not all software applications are the same and may not be enabling for their particular process.

In today's and in the subsequent post, we will visit the current capabilities of manufacturing software from a scheduling perspective and try to establish what exactly to look for when choosing scheduling software or an application which contains a scheduling module. A modern manufacturing plant may be highly complex in the way it operates. Let’s consider an example to understand why manual/spread-sheet based scheduling may completely fail for such plants, in addition to what software should be used for scheduling and why. In a modern plant manufacturing say, pharmaceuticals, there might be at-least a few types/categories of products being manufactured which may further be divided into different variants. Being produced using a set of unique and common- material, machine and manual input, there may be numerous recipes for each product variant and type which might provide a unique end product. However there may contain commonalities of routes or activities or operations which may remain common irrespective of the product.

Imagine that this plant gets a tactical schedule from its ERP which provides details of work orders, BOMs, inventory status, etc., although currently the plant does not have any software application for operational/production scheduling and relies on planners working with spread-sheets for production schedules. For an automated plant such as the one in consideration as of now, there can be thousands of different combinations or recipes and routes, which may overlap and intersect for enabling the production of the entire product range being offered. In addition to these, there can be any customized orders being made for an R&D lab or another facility for testing or simply a variant/combination product, which may require further overlap of process inputs.

This complex interplay of the material, machine and manpower makes scheduling in the plant, what is referred to as an NP-Hard problem. Here data sets and objectives are so large and no optimal computation of the schedule could be calculated as it would require infinite time. In such complex situations, the planners can at best perform a very reactive scheduling, which is incapable of flexibility, demanded by modern manufacturing conditions and factors such are ever-changing demands, customization, and equipment down-time and so on. In such a plant, schedules made would not be able to accommodate contingencies or guide operational personnel as to what is the next best thing to do, as they are just plans made considering the capacity of the operation, orders in hand and assuming that there will be no contingent break-down, shortage, or any other issue. For a modern, fully automated plant, this would be a very reactive way to function and would cause major losses if multiple issues happen in the production line and the planner doesn't receive the information in time to reschedule or re-prioritize the entire schedule. Such an event may derail the entire tactical schedule and drastically erode the profits of the plant.

So, the obvious question here is if the problem of scheduling is so complex that it will take an infinite time to compute, how to schedule jobs in such a plant? This will be explored in our next blog post on scheduling. Stay tuned!

< back


IIoT Has a "Thing" for MES. Why IoT Platforms Won’t Replace MES for Industry 4.0
by Iyno Advisors and Critical Manufacturing