Algorithms for Controlling Palletizers

Palletizers are widely used in delivery industry. We consider a large palletizer where each stacker crane grabs a bin from one of k conveyors and position it onto a pallet located at one of p stack-up places. All bins have the same size. Each pallet is destined for one customer. A completely stacked pallet will be removed automatically and a new empty pallet is placed at the palletizer. The FIFO Stack-Up problem is to decide whether the bins can be palletized by using at most p stack-up places. We introduce a digraph and a linear programming model for the problem. Since the FIFO Stack-Up problem is computational intractable and is defined on inputs of various informations, we study the parameterized complexity. Based on our models we give xp-algorithms and fpt-algorithms for various parameters, and approximation results for the problem.