An approximation algorithm for the stack-up problem

An approximation algorithm for the stack-up problem

0.00 Avg rating0 Votes
Article ID: iaor20013418
Country: Germany
Volume: 51
Issue: 2
Start Page Number: 203
End Page Number: 233
Publication Date: Jan 2000
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: ,
Keywords: optimization
Abstract:

We consider the combinatorial stack-up problem motivated by stacking up bins from a conveyor onto pallets. The stack-up problem is to decide whether a given list q of labeled objects can be processed by removing step by step one of the first s objects of q so that the following holds. After each removal there are at most p labels for which the first object is already removed from q and the last object is still contained in q. We give some NP-completeness results and we introduce and analyze a polynomial time approximation algorithm for the stack-up problem.

Reviews

Required fields are marked *. Your email address will not be published.