On the complexity of the FIFO stack-up problem

Frank Gurski (), Jochen Rethmann () and Egon Wanke ()

Mathematical Methods of Operations Research, 2016, vol. 83, issue 1, 33-52

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, \ldots , q_k$$ 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$$ 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. Copyright Springer-Verlag Berlin Heidelberg 2016

Keywords: Computational complexity; Combinatorial optimization; Directed pathwidth; Discrete algorithms (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-015-0518-9 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:83:y:2016:i:1:p:33-52

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-015-0518-9

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().