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 are k sequences \(q_1, \ldots , q_k\) 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. In this paper we consider on-line algorithms for instances where we only know the next c bins of every sequence instead of the complete sequences. We implemented our algorithms and could show that for realistic, but randomly generated instances our best approach leads only 12% more stack-up places than an optimal off-line solution. On the other hand we could show worst-case examples which show an arbitrary large competitive factor when comparing our on-line solutions with optimal off-line solutions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
de Koster, R.: Performance approximation of pick-to-belt orderpicking systems. Eur. J. Oper. Res. 92, 558–573 (1994)
Rethmann, J., Wanke, E.: Storage controlled pile-up systems, theoretical foundations. Eur. J. Oper. Res. 103(3), 515–530 (1997)
Gurski, F., Rethmann, J., Wanke, E.: Moving bins from conveyor belts onto pallets using FIFO queues. In: Operations Research Proceedings (OR 2013), Selected Papers, pp. 185–191. Springer (2014)
Gurski, F., Rethmann, J., Wanke, E.: A practical approach for the FIFO stack-up problem. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, Advances in Intelligent Systems and Computing, vol. 360, pp. 141–152. Springer (2015)
Gurski, F., Rethmann, J., Wanke, E.: Algorithms for controlling palletizers. In: Operations Research Proceedings (OR 2014), Selected Papers, pp. 197–203. Springer (2016)
Gurski, F., Rethmann, J., Wanke, E.: On the complexity of the fifo stack-up problem. Math. Meth. Oper. Res. 83(1), 33–52 (2016)
Gurski, F., Rethmann, J., Wanke, E.: An experimental study of algorithms for controlling palletizers. In: Operations Research Proceedings (OR 2015), Selected Papers, pp. 27–34. Springer (2017)
Borodin, A.: On-Line Computation and Competitive Analysis. Cambridge University Press (1998)
Fiat, A., Woeginger, G.: Online Algorithms: The State of the Art. LNCS, vol. 1442. Springer (1998)
Gurski, F., Rethmann, J., Wanke, E.: Integer programming models and parameterized algorithms for controlling palletizers. ACM Comput. Res. Repository (CoRR) (2015). arXiv:1509.07278
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Gurski, F., Rethmann, J., Wanke, E. (2018). On-Line Algorithms for Controlling Palletizers. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-55702-1_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55701-4
Online ISBN: 978-3-319-55702-1
eBook Packages: Business and ManagementBusiness and Management (R0)