A stochastic online algorithm for unloading boxes from a conveyor line

Reinhard Bürgy (), Pierre Baptiste (), Alain Hertz (), Djamal Rebaine () and André Linhares ()
Additional contact information
Reinhard Bürgy: GERAD & École Polytechnique de Montréal
Pierre Baptiste: GERAD & École Polytechnique de Montréal
Alain Hertz: GERAD & École Polytechnique de Montréal
Djamal Rebaine: GERAD & Université du Québec à Chicoutimi
André Linhares: University of Waterloo

Flexible Services and Manufacturing Journal, 2018, vol. 30, issue 4, No 6, 764-784

Abstract: Abstract This article discusses the problem of unloading a sequence of boxes from a single conveyor line with a minimum number of moves. The problem under study is efficiently solvable with dynamic programming if the complete sequence of boxes is known in advance. In practice, however, the problem typically occurs in a real-time setting where the boxes are simultaneously placed on and picked from the conveyor line. Moreover, a large part of the sequence is often not visible. As a result, only a part of the sequence is known when deciding which boxes to move next. We develop an online algorithm that evaluates the quality of each possible move with a scenario-based stochastic method. Two versions of the algorithm are analyzed: in one version, the quality of each scenario is measured with an exact method, while a heuristic technique is applied in the second version. We evaluate the performance of the proposed algorithms using extensive computational experiments and establish a simple policy for determining which version to choose for specific problems. Numerical results show that the proposed approach consistently provides high-quality results, and compares favorably with the best known deterministic online algorithms. Indeed, the new approach typically provides results with relative gaps of 1–5% to the optimum, which is about 20–80% lower than those obtained with the best deterministic approach.

Keywords: Sequencing; Real-time scheduling; Heuristics; Conveyor line; Stochastic online optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10696-017-9291-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:flsman:v:30:y:2018:i:4:d:10.1007_s10696-017-9291-9

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

DOI: 10.1007/s10696-017-9291-9

Access Statistics for this article

Flexible Services and Manufacturing Journal is currently edited by Hans Günther

More articles in Flexible Services and Manufacturing Journal from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().