Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld


Controlling Distribution Conveyors and Multi-Line Palletizers: Theoretical Foundations and Online Algorithms.
OR Spectrum, 41(2): 581-611, 2019

F. Gurski
C. Rehs
J. Rethmann
E. Wanke

Abstract

We consider the Distribution problem for multi-line palletizing systems which arises in centralized distribution centers, where boxes have to be stacked-up from conveyor belts onto pallets with respect to customer orders. The problem asks how to distribute boxes to k buffer queues such that an optimal subsequent stacking process requires only p stack-up places. The boxes reach the palletizer on the main conveyor of an order-picking system. A distribution conveyor pushes the boxes out to several buffer conveyors. Robotic arms are placed at the end of these buffer conveyors, where each arm picks up the first box of one of the buffer conveyors and moves it onto a pallet located at one of p stack-up places.
In this paper, we seek for an assignment of the boxes from the main conveyor to the buffer conveyors such that only p stack-up places are used during the subsequent stacking process. We present online algorithms and analyze their worst-case behaviour. For restricted problems, an optimal online algorithm is given, which also performs very well for general instances. The average-case behaviour is determined by experiments. For benchmarking the general case, we present two binary integer programs. The Distribution problem for stacking systems has not been investigated up to now, although it is a natural problem to consider.
Key words: binary integer program, combinatorial optimization, computational complexity, online algorithms, palletizing systems, stacking systems