On the complexity of the FIFO stack-up problem

Frank Gurski (), Jochen Rethmann () and Egon Wanke ()
Additional contact information
Frank Gurski: University of Düsseldorf, Institute of Computer Science
Jochen Rethmann: Niederrhein University of Applied Sciences
Egon Wanke: University of Düsseldorf, Institute of Computer Science

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

Abstract: 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.

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://link.springer.com/10.1007/s00186-015-0518-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:d:10.1007_s00186-015-0518-9

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 ().