Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Mathematical methods of operations research (Heidelberg, Germany), 2016-02, Vol.83 (1), p.33-52
Ort / Verlag
Berlin/Heidelberg: Springer Berlin Heidelberg
Erscheinungsjahr
2016
Quelle
EBSCOhost Business Source Ultimate
Beschreibungen/Notizen
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.