On the complexity of the FIFO stack-up problem

DOI10.1007/S00186-015-0518-9MaRDI QIDQ261535zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Jochen Rethmann, Egon Wanke

Publication date 24 March 2016

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.1915

zbMATH Keywords

computational complexitycombinatorial optimizationdirected pathwidthdiscrete algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)

Abstract: We study the combinatorial FIFO stack-up problem. In delivery industry, bins have to be stacked-up from conveyor belts onto pallets with respect to customer orders. Given k sequences q_1, ..., q_k of labeled bins and a positive integer p, the aim is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto an initially empty pallet of unbounded capacity located at one of p stack-up places. Bins with different pallet labels have to be placed on different pallets, bins with the same pallet label have to be placed on the same pallet. After all bins for a pallet have been removed from the given sequences, the corresponding stack-up place will be cleared and becomes available for a further pallet. The FIFO stack-up problem is to find a stack-up sequence such that all pallets can be build-up with the available p stack-up places. In this paper, we introduce two digraph models for the FIFO stack-up problem, namely the processing graph and the sequence graph. We show that there is a processing of some list of sequences with at most p stack-up places if and only if the sequence graph of this list has directed pathwidth at most p-1. This connection implies that the FIFO stack-up problem is NP-complete in general, even if there are at most 6 bins for every pallet and that the problem can be solved in polynomial time, if the number p of stack-up places is assumed to be fixed. Further the processing graph allows us to show that the problem can be solved in polynomial time, if the number k of sequences is assumed to be fixed.

Recommendations

• A practical approach for the FIFO stack-up problem
• On the hardness of palletizing bins using FIFO queues
• An Experimental Study of Algorithms for Controlling Palletizers
• Algorithms for controlling palletizers
• Stack-up algorithms for palletizing at delivery industry

Cites work

• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• A practical approach for the FIFO stack-up problem
• An approximation algorithm for the stack-up problem
• Computing Directed Pathwidth in O(1.89 n ) Time
• Directed tree-width
• Min Cut is NP-complete for edge weighted trees
• On the complexity of the FIFO stack-up problem
• Online algorithms. The state of the art
• Performance approximation of pick-to-belt orderpicking systems
• Stack-up algorithms for palletizing at delivery industry
• Storage controlled pile-up systems, theoretical foundations

Cited in

(9)

• On the complexity of the FIFO stack-up problem
• On the hardness of palletizing bins using FIFO queues
• An approximation algorithm for the stack-up problem
• Characterizations and directed path-width of sequence digraphs
• A practical approach for the FIFO stack-up problem
• The stack loading and unloading problem
• Synchronized pickup and delivery problems with connecting FIFO stack
• Controlling distribution conveyors and multiline palletizers: theoretical foundations and online algorithms
• Directed pathwidth and palletizers

This page was built for publication: On the complexity of the FIFO stack-up problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q261535)