TY - JOUR

T1 - A new heuristic and an exact approach for a production planning problem

AU - Auer, Peter

AU - Dósa, György

AU - Dulai, Tibor

AU - Fügenschuh, Armin

AU - Näser, Peggy

AU - Ortner, Ronald

AU - Werner-Starkne, Agnes

N1 - Publisher Copyright: © 2020, The Author(s).

PY - 2021/9

Y1 - 2021/9

N2 - We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The complexity of the problem arises from having a huge number of products from both types. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. We consider a special case, where there are two job types on four different tasks, and four types of machines. Some of the machines are multi-purpose and some operations can be processed by different machine types. The processing time of an operation may depend also on the machine that processes it. The problem is very difficult to solve even in this special setting. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct influence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time.

AB - We deal with a very complex and hard scheduling problem. Two types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The complexity of the problem arises from having a huge number of products from both types. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. We consider a special case, where there are two job types on four different tasks, and four types of machines. Some of the machines are multi-purpose and some operations can be processed by different machine types. The processing time of an operation may depend also on the machine that processes it. The problem is very difficult to solve even in this special setting. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct influence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time.

UR - http://www.scopus.com/inward/record.url?scp=85086380356&partnerID=8YFLogxK

UR - https://pure.unileoben.ac.at/portal/en/publications/a-new-heuristic-and-an-exact-approach-for-a-production-planning-problem(941c638e-e716-4897-9ed1-7616f3190f4b).html

U2 - 10.1007/s10100-020-00689-3

DO - 10.1007/s10100-020-00689-3

M3 - Article

VL - 29

SP - 1079

EP - 1113

JO - Central European Journal of Operations Research

JF - Central European Journal of Operations Research

SN - 1435-246X

IS - 3

ER -