Modeling and Solving the K-track Assignment Problem

Abstract

In the industrial production of cleaning supplies, larger production quantities are stored in storage boilers and from there they are filled into household-sized bottles. An interesting problem arises in the planning of this process in which production orders have to be assigned to these storage boilers at predetermined times. It turns out that this problem corresponds to a variant of the problem known in the literature as the k-track assignment problem or operational fixed job scheduling problem (OFJSP), which is a classical NP-hard optimization problem. In this paper we investigate and compare different modeling approaches including a CP model, a direct ILP model, a network flow based reformulation as well as a simulated annealing approach. We evaluate these methods on a large set of instances for this problem and on benchmark instances for a related problem. We show that the simulated annealing approach provides very good solutions and outperforms other known solution approaches for larger instances. Our methods have been applied in real-life scenarios, where they have been able to obtain optimal solutions in a short time.