SKU assignment in a multiple picking line order picking system.
Date
2015-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: An order picking system in a distribution center (DC) owned by Pep Stores Ltd. (PEP) is
investigated. Twelve unidirectional picking lines situated in the center of the DC are used to
process all piece picking. Each picking line consists of a number of locations situated in a
cyclical formation around a central conveyor belt. Pickers walk in a clockwise direction around
a conveyor belt picking stock for stores.
The picking lines are managed in waves due to PEPs policy to push stock to stores. For each
wave of picking a subset of released stock keeping units (SKUs) is selected and assigned to an
available picking line. The physical stock is then brought to the assigned picking line before
multiple pickers pick all the store requirements (or orders) de ned by the SKUs within that
wave. Once all of the orders have been picked a new mutually exclusive set of SKUs, de ning
a new wave, is brought to the picking line for picking. In this way picking lines function in
parallel to and independently of each other.
The order picking system is deconstructed into three decision tiers. Firstly at the start of each
day SKUs are assigned to available picking lines which de nes the Picking Line Assignment
Problem (PLAP). Once a set of SKUs has been assigned to a picking line each SKU is assigned
a speci c location within the picking line which de nes the SKU Location Problem (SLP).
Finally once pickers are brought to the picking line the individual orders are sequenced for each
picker. This de nes the Order Sequencing Problem (OSP). The focus of this dissertation is on
the rst two subproblems namely, the SLP and PLAP as the OSP has already been solved in a
previous study.
This picking line setup considered here has many similarities to carousel systems. Several
heuristic approaches for arranging SKUs within carousel systems are adapted for use in this
picking line environment. These heuristics are compared to two novel lower bound formulations
as well as trivial lower bound to evaluate their performance. Both historical as well as generated
problem instances are used to compare the relative performances of each heuristic. An average
saving of 2% for large and 6.5% for medium sized problem instances is achieved if the best
solution form the four heuristics is selected. Three goals are used when assigning SKUs to
picking lines in the PLAP. Firstly walking distance should be reduced, secondly the number of
small cartons produced should be minimal and nally the number of pallet movements required
to populate any one picking line for a wave of picking should be manageable.
The concept of a maximal cut is used as an estimate for total walking distance and it is shown
that by minimising the maximal cut within each picking line the total walking distance is
reduced. A greedy phased insertion heuristic is introduced which minimised the maximal cut
and therefore walking distance. Although the total walking distance was reduced by on average
22% compared to historical assignments the number of small cartons produced and the number
of pallet movements required to populate some picking lines is undesirable.
Four measures using SKU correlations are introduced and used within a phased greedy insertion
framework. These measures reduce the number of small cartons produced with a marginal increase
in total walking distance compared to approaches which minimized the maximal cut only.
The total walking distance is reduced by on average 20% compared to historical assignments
with the number of small cartons produced within an acceptable range. However, the number
of pallet movements required to populate some of the picking lines remains at an undesirable
level.
A nal picking line segmentation approach is introduced using a sequence of integer programming
formulations. These formulations include capacity constraints which limit the total volume
of stock (and therefore the number of pallet movements) assigned to any one picking line. This
approach delivers individual picking lines that have a manageable number of pallet movements
to populate all picking lines with stock. A nal hybrid approach is also introduced which
switches between this segmentation approach and a correlations approached when appropriate.
This results in a 15% reduction in walking distance compared to historical assignments while
maintaining a good number of small cartons produced and improving on the historical assignments
in terms of the number of pallet movements required to populate any one picking line
with stock.
The managers within the DC are responsible for doing both the SKU to picking line assignments
as well as the SKU arrangements within each picking line. A new warehouse management
system (WMS) is in the process of design and implementation. A proof of concept interface
which illustrated how the approaches to both the SLP and PLAP can be implemented in the
new WMS while still allowing for managerial
exibility is therefore proposed.
AFRIKAANSE OPSOMMING: 'n Bestellinguitsoekstelsel in 'n distribusiesentrum wat deur Pep Stores Bpk. (PEP) besit word, word ondersoek. PEP gebruik twaalf eenrigting uitsoeklyne wat in die distribusie sentrum is om al die items vir bestellings uit te soek. Elke uitsoeklyn bestaan uit 'n aantal vakkies wat rondom voerband gele e is. Werkers loop in 'n kloksgewyse rigting om hierdie voerband om items vir winkels te versamel. Die uitsoeklyne opereer in golwe omdat PEP 'n beleid het om voorraad na die winkels te stuur (eerder as dat winkels voorraad bestel). 'n Subversameling van beskikbare voorraadeenhede (VE's) word geselekteer en toegewys aan 'n beskikbare uitsoeklyn. Die voorraad word dan na die toegewysde uitsoeklyn gebring voordat 'n aantal werkers al die bestellings (wat deur die VE's in daardie golf gede nieer word) vir die winkels gaan versamel. Indien al die bestelling in daardie golf voltooi is, word 'n nuwe onderling uitsluitende versameling VE's na die uitsoeklyn gebring, wat dan weer 'n nuwe golf vorm. Op hierdie manier kan die uitsoeklyne parallel aan, en onafhanklik van mekaar funksioneer. Hierdie uitsoekstelsel kan ontbind word in drie vlakke van besluitneming. In die eerste vlak word VE's aan beskikbare lyne toegwys, wat gede nieer word as die uitsoeklyntoewysingsprobleem (PLAP). Nadat die VE's aan die lyn toegewys is, moet elke VE aan 'n spesi eke vakkie binne daardie lyn toegewys word en word gede nieer as die VE-plasingsprobleem (SLP). In die derde vlak moet die bestellings se volgorde bepaal word vir die opmaak van die bestellings. Dit word as die bestellingvolgordeprobleem (OSP) gede nieer. Die fokus van hierdie proefskrif is op die eerste twee vlakke van besluitneming, naamlik die PLAP en SLP. Die OSP is reeds in vorige studies opgelos. Die uitsoekstel wat hier beskou word het baie ooreenkomste met 'n rondomtaliestelsel. 'n Aantal heuristiese benaderings tot die rangskikking van van VE's in vakkies vir rondomtaliestelsels word aangepas en ondersoek vir hierdie uitsoekstelsel. Hierdie heuristieke word vergelyk met twee nuwe ondergrensformulerings sowel as 'n triviale ondergrens. Historise data en genereerde data word gebruik om die prestasie van elke heuristiek te vergelyk. 'n Gemiddelde besparing van 2% vir groot en 9.5% vir medium opmaaklyne word verkry indien die beste oplossing van die vier heuristieke gekies word. Drie doelwitte word beskou indien VE's aan opmaaklyne toegewys word (tydens PLAP). Eerstens moet die stapafstand van werkers geminimeer word, tweedens moet die aantal klein kartonne geminimeer word en laastens moet die hoeveelheid werk (vurkhyserbewegings) om die voorraad na 'n enkele lyn te bring binne perke gehou word. Die beginsel van 'n maksimum snit word gebruik om die stapafstand te benader en resultate toon duidelik dat deur die maksimum snit te minimeer word die stapafstand ook verminder. 'n Gulsige gefaseerde invoegingsheuristiek (GP) word voorgestel wat die maksimum snit te minimeer. Alhoewel die totale stapafstand met 22% verminder teeenoor historiese data vermeerder die aantal klein kartonne en die aantal vurkhyserbewegins na sekere lyne word onaanvaarbaar hoog. Vier maatstawwe om die korrelasies/verwantskappe tussen VE's te bereken word vervolgens gebruik in die GP heuristiek om VE's in lyne toe te wys. Hierdie maatstawwe verbeter die aantal klein kartonne met 'n marginale toename in stapafstand teenoor die metodes wat slegs die maksimum snit minimeer. Die totale stapafstand word nou slegs verminder met 20%, maar die aantal klein kartonne val binne 'n aanvaarbare perk. Die aantal vurkhyserbewegings na sommige lyne is egter steeds te hoog. 'n Segmenteringsbenadering word voorgestel waarin 'n aantal heeltalige programmeringsformulerings gebruik word. Hierdie formulerings sluit kapasiteitsbeperkings in wat die totale volume voorraad na 'n uitsoeklyn beperk. Hierdie formulerings lewer uitsoeklyne wat 'n aanvaarbare hoeveelheid vurkhyserbewegings benodig. 'n Finale hibriedbenadering word ook voorgestel wat 'n kombinasie van die segmentering- en korrelasiebenadering gebruik. Hierdie metode verskaf 'n 15% verbetering in stapafstand relatief tot historiese oplossings terwyl 'n goeie aantal klien kartonne gehandhaaf en daar verbeter word op die aantal vurhyserbewegings. Die uitsoeklynbestuurders is verantwoordelik vir die oplossing van die PLAP en die SLP. 'n Nuwe pakhuisbestuurstelsel (WMS) is in die proses van implementering by PEP. 'n Voorstel van hoe hierdie oplossingmetodes in die WMS ingesluit en hoe die gebruikerskoppelvlak moet lyk sodat daar steeds 'n groot mate van vryheid aan die gebruiker oorgelaat word, word ook verskaf.
AFRIKAANSE OPSOMMING: 'n Bestellinguitsoekstelsel in 'n distribusiesentrum wat deur Pep Stores Bpk. (PEP) besit word, word ondersoek. PEP gebruik twaalf eenrigting uitsoeklyne wat in die distribusie sentrum is om al die items vir bestellings uit te soek. Elke uitsoeklyn bestaan uit 'n aantal vakkies wat rondom voerband gele e is. Werkers loop in 'n kloksgewyse rigting om hierdie voerband om items vir winkels te versamel. Die uitsoeklyne opereer in golwe omdat PEP 'n beleid het om voorraad na die winkels te stuur (eerder as dat winkels voorraad bestel). 'n Subversameling van beskikbare voorraadeenhede (VE's) word geselekteer en toegewys aan 'n beskikbare uitsoeklyn. Die voorraad word dan na die toegewysde uitsoeklyn gebring voordat 'n aantal werkers al die bestellings (wat deur die VE's in daardie golf gede nieer word) vir die winkels gaan versamel. Indien al die bestelling in daardie golf voltooi is, word 'n nuwe onderling uitsluitende versameling VE's na die uitsoeklyn gebring, wat dan weer 'n nuwe golf vorm. Op hierdie manier kan die uitsoeklyne parallel aan, en onafhanklik van mekaar funksioneer. Hierdie uitsoekstelsel kan ontbind word in drie vlakke van besluitneming. In die eerste vlak word VE's aan beskikbare lyne toegwys, wat gede nieer word as die uitsoeklyntoewysingsprobleem (PLAP). Nadat die VE's aan die lyn toegewys is, moet elke VE aan 'n spesi eke vakkie binne daardie lyn toegewys word en word gede nieer as die VE-plasingsprobleem (SLP). In die derde vlak moet die bestellings se volgorde bepaal word vir die opmaak van die bestellings. Dit word as die bestellingvolgordeprobleem (OSP) gede nieer. Die fokus van hierdie proefskrif is op die eerste twee vlakke van besluitneming, naamlik die PLAP en SLP. Die OSP is reeds in vorige studies opgelos. Die uitsoekstel wat hier beskou word het baie ooreenkomste met 'n rondomtaliestelsel. 'n Aantal heuristiese benaderings tot die rangskikking van van VE's in vakkies vir rondomtaliestelsels word aangepas en ondersoek vir hierdie uitsoekstelsel. Hierdie heuristieke word vergelyk met twee nuwe ondergrensformulerings sowel as 'n triviale ondergrens. Historise data en genereerde data word gebruik om die prestasie van elke heuristiek te vergelyk. 'n Gemiddelde besparing van 2% vir groot en 9.5% vir medium opmaaklyne word verkry indien die beste oplossing van die vier heuristieke gekies word. Drie doelwitte word beskou indien VE's aan opmaaklyne toegewys word (tydens PLAP). Eerstens moet die stapafstand van werkers geminimeer word, tweedens moet die aantal klein kartonne geminimeer word en laastens moet die hoeveelheid werk (vurkhyserbewegings) om die voorraad na 'n enkele lyn te bring binne perke gehou word. Die beginsel van 'n maksimum snit word gebruik om die stapafstand te benader en resultate toon duidelik dat deur die maksimum snit te minimeer word die stapafstand ook verminder. 'n Gulsige gefaseerde invoegingsheuristiek (GP) word voorgestel wat die maksimum snit te minimeer. Alhoewel die totale stapafstand met 22% verminder teeenoor historiese data vermeerder die aantal klein kartonne en die aantal vurkhyserbewegins na sekere lyne word onaanvaarbaar hoog. Vier maatstawwe om die korrelasies/verwantskappe tussen VE's te bereken word vervolgens gebruik in die GP heuristiek om VE's in lyne toe te wys. Hierdie maatstawwe verbeter die aantal klein kartonne met 'n marginale toename in stapafstand teenoor die metodes wat slegs die maksimum snit minimeer. Die totale stapafstand word nou slegs verminder met 20%, maar die aantal klein kartonne val binne 'n aanvaarbare perk. Die aantal vurkhyserbewegings na sommige lyne is egter steeds te hoog. 'n Segmenteringsbenadering word voorgestel waarin 'n aantal heeltalige programmeringsformulerings gebruik word. Hierdie formulerings sluit kapasiteitsbeperkings in wat die totale volume voorraad na 'n uitsoeklyn beperk. Hierdie formulerings lewer uitsoeklyne wat 'n aanvaarbare hoeveelheid vurkhyserbewegings benodig. 'n Finale hibriedbenadering word ook voorgestel wat 'n kombinasie van die segmentering- en korrelasiebenadering gebruik. Hierdie metode verskaf 'n 15% verbetering in stapafstand relatief tot historiese oplossings terwyl 'n goeie aantal klien kartonne gehandhaaf en daar verbeter word op die aantal vurhyserbewegings. Die uitsoeklynbestuurders is verantwoordelik vir die oplossing van die PLAP en die SLP. 'n Nuwe pakhuisbestuurstelsel (WMS) is in die proses van implementering by PEP. 'n Voorstel van hoe hierdie oplossingmetodes in die WMS ingesluit en hoe die gebruikerskoppelvlak moet lyk sodat daar steeds 'n groot mate van vryheid aan die gebruiker oorgelaat word, word ook verskaf.
Description
Thesis (PhD)--Stellenbosch University, 2015.
Keywords
Combinatorical optimisation, Warehouses -- Management, UCTD, Order picking systems, Stock keeping units, Pep Stores Ltd.