Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic

Date

2019-02-01

Author

ÇELİK, MELİH
Süral, Haldun

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

213
views

0
downloads

In this paper, we consider the order picking problem (OPP), which constitutes one of the special cases of the Steiner travelling salesperson problem and addresses the costliest operation in a warehouse. Given a list of items to be picked and their locations in the warehouse layout, the OPP aims to find the shortest route that starts from a depot point, picks all the items in the list, and returns to the depot. This paper fills two important gaps regarding the OPP. First, to the best of our knowledge, we present the first complexity results on the problem. Second, we propose a heuristic approach that makes use of its graph-theoretic properties. Computational experiments on randomly generated instances show that the heuristic not only outperforms its state-of-the-art counterparts in the literature, but it is also robust in terms of changing problem parameters.

Subject Keywords

Management Science and Operations Research, Strategy and Management, Industrial and Manufacturing Engineering

URI

https://hdl.handle.net/11511/42993

Journal

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH

DOI

https://doi.org/10.1080/00207543.2018.1489154

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

JOB-SHOP SCHEDULING UNDER A NONRENEWABLE RESOURCE CONSTRAINT TOKER, A; KONDAKCI, S; ERKIP, N (JSTOR, 1994-08-01) In this paper we consider the job shop scheduling problem under a discrete non-renewable resource constraint. We assume that jobs have arbitrary processing times and resource requirements and there is a unit supply of the resource at each time period. We develop an approximation algorithm for this problem and empirically test its effectiveness in finding the minimum makespan schedules.
Spread time considerations in operational fixed job scheduling Eliiyi, D. T.; Azizoğlu, Meral (Informa UK Limited, 2006-10-15) In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance c...
Scheduling parallel machines to minimize weighted flowtime with family set-up times Azizoğlu, Meral (Informa UK Limited, 2003-01-01) We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time.
Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...
Generating all efficient solutions of a rescheduling problem on unrelated parallel machines Ozlen, Melih; Azizoğlu, Meral (Informa UK Limited, 2009-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and stability measures. Our efficiency measure is the total flow time and stability measure is the total reassignment cost caused by the differences in the machine allocations in the initial and new schedules. We propose a branch and bound algorithm to generate all efficie...

Citation Formats

M. ÇELİK and H. Süral, “Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic,” INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, pp. 888–906, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/42993.