Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
A Practical Approach for the FIFO Stack-Up Problem
MCO 2015 (Advances in Intelligent Systems and Computing, pp 141-152)
Abstract
| We consider the FIFO Stack-Up problem which arises in delivery industry, where bins have to be stacked-up from conveyor belts onto pallets. Given k sequences q1, …, qk of labeled bins and a positive integer p. The goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-up problem is computational intractable [F. Gurski, J. Rethmann, and E. Wanke. Complexity of the FIFO Stack-Up problem. ACM Computing Research Repository (CoRR), abs/1307.1915, 2013.]. |
| In this paper we introduce a graph model for this problem, which allows us to show a breadth first search solution. Our experimental study of running times shows that our approach can be used to solve a lot of practical instances very efficiently. |