by Markus Berg (proALPHA) and Sebastian Velten (Fraunhofer ITWM)
In complex production environments, understanding the results of a scheduling algorithm is a challenging task. To avoid tardy work orders, proALPHA and Fraunhofer ITWM developed a component for identifying practical tardiness reasons and appropriate countermeasures.
The proALPHA group is the third largest ERP provider for small and mid-sized manufacturing and trading companies in Germany, Austria, and Switzerland. For more than 25 years, proALPHA has offered a powerful ERP solution as well as consulting, support, training, and maintenance services from one source. The flexible and scalable ERP solution features a wide range of functions that allow all processes along the value-added chain to be controlled.
One of the modules available for the proALPHA ERP solution is Production. The goal of this module is the organization of the whole production process (from prefabrication to final products) of a company by providing decision support for production planners. To this end, work orders (consisting of structured process steps), calendars for production resources (workforces, machines, tools), material levels (with reorder times and known in- and outflows) and resource as well as material requirements can be managed. In addition, the module contains various production planning and detailed scheduling algorithms.
These algorithms can be used to execute a complete optimization of all work orders with respect to current resource and material availabilities. The considered problem is a (multi-) resource constrained multi-project scheduling problem (see [1]) with several additional features: resource and overload decisions, producer/consumer assignments and time bounds among others. The objectives are the minimization of tardiness, earliness and throughput time of the work orders. To model and solve the problem a Constraint Programming approach (see [2]) is used. For the implementation, the CP-library IBM ILOG CP Optimizer (see [3]) is employed.
Since the complete optimization takes limited resource and material capacities into account, tardy processes can typically not be avoided. In many cases, this is not acceptable, as tardy processes violate contracts or delivery promises made to important customers. Therefore, one of the main tasks of a production planner is to identify why a particular process is scheduled too late and what he or she can do to make a production in time possible. This task, however, is not easy as, for example, customer orders often require many production resources, raw materials and prefabrication steps.
To support the production planner in this critical task, the complete optimization has been extended by a tardiness-reasoning component, which provides tardiness reasons with respect to the optimized schedule. From a mathematical point of view, a tardiness reason of a process is a minimal set of constraints, which, together with the constraint that the process ends in time, is infeasible. However, the determination of such minimal infeasible sets is, in general, a hard problem and minimal sets alone are of limited use.
From a practical point of view, tardiness reasons are nearly always rather simple and can be divided in different reason-types:
- Structure: Processing times together with precedence constraints lead to a delay.
- Time Bound: A time bound (release dates) leads to a delay.
- Single Material: A missing material leads to a delay.
- Single Resource: A resource with missing capacity leads to a delay.
- Combined: A missing material together with a resource or two resources together lead to a delay.
Based on these reason-types, the tardiness-reasoning component works as follows. First, all potential reasons for a tardy process are identified (for example, each consumed material is a potential material reason). Then, for each potential reason it is tested, if it is indeed responsible for a delay. For each reason-type, special constraint based models are used for this test. Finally, if a reason is verified, further information is calculated that help the production planner to evaluate the importance of the reason and give hints on how the problem can be fixed. Examples are the delay caused by a reason, the amount of a material and the latest point in time when it is needed as well as the amount of free time that is missing on a resource (see Figure 1).
Figure 1: Result of the tardiness-reasoning component for a single work order.
Tests with practical data show that far more than 90% of the delays can be explained, even if not all possible reasons are covered. The component helps production planners to identify tardiness reasons as well as bottlenecks (materials, resources). As a result, it leads to a higher acceptance of the schedules provided by the complete optimization.
References:
[1] S. Hartmann, D. Briskorn: “A survey of variants and extensions of the resource constrained project scheduling problem”, European Journal of Operational Research, 207(1), 1-14, 2010.
[2] P. Baptiste, C. Le Pape, W. Nuijten: “Constraint-Based Scheduling – Applying Constraint Programming to Scheduling Problems”, Kluwer, 2001.
[3] P. Laborie, J. Rogerie, P. Shaw, P. Vilím: “IBM ILOG CP optimizer for scheduling, 20+ years of scheduling with constraints at IBM/ILOG”, Constraints, 23, 210 – 250, 2018.
Please contact:
Sebastian Velten
Fraunhofer ITWM, Germany
+49 (0)631 31600 4260
