Order sequencing and SKU arrangement on a unidirectional picking line
Date
2012-03
Authors
Matthews, Jason
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: An order picking operation in a distribution centre (DC) owned by Pep Stores Ltd, located in
Durban, South Africa was considered. The order picking operation utilises picking lines and the
concept of wave picking. A picking line is a central area with storage locations for pallet loads
of stock keeping units (SKUs) around a conveyor belt. The system shows many similarities to
unidirectional carousel systems found in literature, however, the unidirectional carousel system
is not common. Sets of SKUs must be assigned to pick waves. The SKUs associated with a
single wave are then arranged on a picking line after which pickers move in a clockwise direction
around the conveyor belt to pick the orders.
The entire order picking operation was broken into three tiers of decision making and three
corresponding subproblems were identi ed. The rst two subproblems were investigated which
focused on a single picking line. The rst subproblem called the order sequencing problem (OSP)
considered the sequencing of orders for pickers and the second called the SKU location problem
(SLP) the assignment of SKUs to locations in the picking line for a given wave.
A tight lower bound was established for the OSP using the concept of a maximal cut. This
lower bound was transformed into a feasible solution within 1 pick cycle of the lower bound.
The solution was also shown to be robust and dynamic for use in practice. Faster solution times,
however, were required for use in solution techniques for the SLP. Four variations of a greedy
heuristic as well as two metaheuristic methods were therefore developed to solve the problem in
shorter times.
An ant colony approach was developed to solve the SLP. Furthermore, four variations of a
hierarchical clustering algorithm were developed to cluster SKUs together on a picking line
and three metaheuristic methods were developed to sequence these clusters. All the proposed
approaches outperformed known methods for assigning locations to SKUs on a carousel.
To test the validity of assumptions and assess the practicality of the proposed solutions an agent
based simulation model was built. All proposed solutions were shown to be applicable in practice
and the proposed solutions to both subporblems outperformed the current approaches by Pep.
Furthermore, it was established that the OSP is a more important problem, in comparison to
the SLP, for Pep to solve as limited savings can be achieved when solving the SLP.
AFRIKAANSE OPSOMMING: 'n Stelsel vir die opmaak van bestellings in 'n distribusiesentrum van Pep Stores Bpk. in Durban, Suid-Afrika word beskou. Hierdie stelsel gebruik uitsoeklyne waarop bestellings in golwe opgemaak word. 'n Uitsoeklyn is 'n area met vakkies waarop pallette met voorraadeenhede gestoor kan word. Hierdie vakkies is rondom 'n voerband gerangskik. Die stelsel het ooreenkomste met die eenrigting carrousselstelsels wat in die literatuur voorkom, maar hierdie eenrigtingstelsels is nie algemeen nie. Voorraadeenhede moet aan 'n golf toegewys word wat in 'n uitsoeklyn gerangskik word, waarna werkers dan die bestellings in die betrokke golf opmaak. Die hele operasie van bestellings opmaak kan opgebreek word in drie vlakke van besluite met gepaardgaande subprobleme. Die eerste twee subprobleme wat 'n enkele uitsoeklyn beskou, word aangespreek. Die eerste subprobleem, naamlik die volgorde-van-bestellings-probleem (VBP) beskou die volgorde waarin bestellings opgemaak word. Die tweede probeem is die voorraadeenheidaan- vakkie-toewysingsprobleem (VVTP) en beskou die toewysings van voorraadeenhede aan vakkies in 'n uitsoeklyn vir 'n gegewe golf. 'n Sterk ondergrens vir die VBP is bepaal met behulp van die konsep van 'n maksimum snit. Hierdie ondergrens kan gebruik word om 'n toelaatbare oplossing te bepaal wat hoogstens 1 carrousselsiklus meer as die ondergrens het. Hierdie oplossings kan dinamies gebruik word en kan dus net so in die praktyk aangewend word. Vinniger oplossingstegnieke is egter nodig indien die VVTP opgelos moet word. Twee metaheuristiese metodes word dus voorgestel waarmee oplossings vir die VBP vinniger bepaal kan word. 'n Mierkolonie benadering is ontwikkel om die VVTP op te los. Verder is vier variasies van 'n hi erargiese groeperingsalgoritme ontwikkel om voorraadeenhede saam te groepeer op 'n uitsoeklyn. Drie metaheuristieke is aangewend om hierdie groepe in volgorde te rangskik. Al hierdie benaderings vaar beter as bekende metodes om voorraadeenhede op 'n carroussel te rankskik. Om die geldigheid van die aannames en die praktiese uitvoerbaarheid van die oplossings te toets, is 'n agent gebaseerde simulasie model gebou. Daar is bevind dat al die voorgestelde oplossings prakties implementeerbaar is en dat al die metodes verbeter op die huidige werkswyse in Pep. Verder kon vasgestel word die VBP belangriker as die VVTP vir Pep is omdat veel kleiner potensiele besparings met die VVTP moontlik is as met die VBP.
AFRIKAANSE OPSOMMING: 'n Stelsel vir die opmaak van bestellings in 'n distribusiesentrum van Pep Stores Bpk. in Durban, Suid-Afrika word beskou. Hierdie stelsel gebruik uitsoeklyne waarop bestellings in golwe opgemaak word. 'n Uitsoeklyn is 'n area met vakkies waarop pallette met voorraadeenhede gestoor kan word. Hierdie vakkies is rondom 'n voerband gerangskik. Die stelsel het ooreenkomste met die eenrigting carrousselstelsels wat in die literatuur voorkom, maar hierdie eenrigtingstelsels is nie algemeen nie. Voorraadeenhede moet aan 'n golf toegewys word wat in 'n uitsoeklyn gerangskik word, waarna werkers dan die bestellings in die betrokke golf opmaak. Die hele operasie van bestellings opmaak kan opgebreek word in drie vlakke van besluite met gepaardgaande subprobleme. Die eerste twee subprobleme wat 'n enkele uitsoeklyn beskou, word aangespreek. Die eerste subprobleem, naamlik die volgorde-van-bestellings-probleem (VBP) beskou die volgorde waarin bestellings opgemaak word. Die tweede probeem is die voorraadeenheidaan- vakkie-toewysingsprobleem (VVTP) en beskou die toewysings van voorraadeenhede aan vakkies in 'n uitsoeklyn vir 'n gegewe golf. 'n Sterk ondergrens vir die VBP is bepaal met behulp van die konsep van 'n maksimum snit. Hierdie ondergrens kan gebruik word om 'n toelaatbare oplossing te bepaal wat hoogstens 1 carrousselsiklus meer as die ondergrens het. Hierdie oplossings kan dinamies gebruik word en kan dus net so in die praktyk aangewend word. Vinniger oplossingstegnieke is egter nodig indien die VVTP opgelos moet word. Twee metaheuristiese metodes word dus voorgestel waarmee oplossings vir die VBP vinniger bepaal kan word. 'n Mierkolonie benadering is ontwikkel om die VVTP op te los. Verder is vier variasies van 'n hi erargiese groeperingsalgoritme ontwikkel om voorraadeenhede saam te groepeer op 'n uitsoeklyn. Drie metaheuristieke is aangewend om hierdie groepe in volgorde te rangskik. Al hierdie benaderings vaar beter as bekende metodes om voorraadeenhede op 'n carroussel te rankskik. Om die geldigheid van die aannames en die praktiese uitvoerbaarheid van die oplossings te toets, is 'n agent gebaseerde simulasie model gebou. Daar is bevind dat al die voorgestelde oplossings prakties implementeerbaar is en dat al die metodes verbeter op die huidige werkswyse in Pep. Verder kon vasgestel word die VBP belangriker as die VVTP vir Pep is omdat veel kleiner potensiele besparings met die VVTP moontlik is as met die VBP.
Description
Thesis (MSc)--Stellenbosch University, 2012.
Keywords
Order picking, Order sequencing, Combinatorial optimisation, Warehouse optimization, Dissertations -- Logistics, Theses -- Logistics, Dissertations -- Operations research, Theses -- Operations research, Order picking systems