Return to search

2D irregular strip packing at Kohler signs

Thesis (MCom)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Kohler Signs (PTY) Ltd is a sign production company located in Cape Town, South Africa.
They manufacture and install signs for the City of Cape Town and private companies as well
as manufacture advertisement signs to be placed on vehicles. Road signs consist of steel sheets
that are cut and bent to the appropriate size and frame, and an image design, which is cut from
re
ective vinyl, are applied to the bent steel sheet. The image design consists of various letters,
numbers and symbols which are categorised as irregular items. When these irregular items are
combined in a distinctive way, with the use of di erent coloured vinyl, they convey a message to
the road user which may be to yield for pedestrians crossing the street, or indicate to the road
user the various highway exits that exist on the interchange ahead. These irregular items are
placed upon re
ective vinyl for cutting which results in vinyl o cuts that are wasted. The focus
of this thesis is to minimise the waste incurred by placing these irregular items upon the vinyl
in an optimal and timely manner for industry use. The vinyl printer, which cuts the irregular
items out of the vinyl, consists of a xed width and is only limited in height by the vinyl itself.
Thus, this problem may be described as a Two Dimensional Irregular Strip Packing Problem.
These irregular items have only a few possible heights for each type of irregular item packed,
which allows these irregular items to be packed as a level packing problem. The items are packed
within levels as though they are regular items with the assistance of a prede ned rule-set. In
this thesis various packing algorithms and image processing methodologies from the literature
are researched and used to develop a new packing algorithm for this speci c problem. The newly
developed algorithm is put through various benchmarks to test its performance. Some of these
benchmarks are procured from Kohler Signs themselves, whereas others are randomly generated
under certain conditions. These benchmarks reveal that the newly developed algorithm performs
better for both the minimisation of waste and the minimisation of algorithm running time than
the tried and trusted techniques utilised in industry by Kohler Signs. / AFRIKAANSE OPSOMMING: Kohler Signs (EDMS) Bpk is 'n padteken produksie maatskappy gele e in Kaapstad, Suid-Afrika.
Hulle vervaardig en installeer tekens vir die Stad van Kaapstad en privaat maatskappye, sowel
as advertensietekens wat op voertuie geplaas word. Padtekens bestaan uit staalplate wat gesny
en gebuig word tot die toepaslike grootte en vorm. 'n Beeldontwerp, wat gesny is uit re
ektiewe
viniel, word vasgesit op die gebuigde staalplaat. Die beeldontwerp bestaan uit verskeie letters,
getalle en simbole wat geklassi seer word as onre elmatige items. Wanneer hierdie onre elmatige
items gekombineer word op 'n eiesoortige manier, met die gebruik van verskillende kleure viniel,
dra hulle 'n boodskap oor aan die padgebruiker, soos byvoorbeeld om toe te gee aan voetgangers
by 'n voetoorgang of dit dui aan die padgebruiker die verskillende snelweguitgange wat bestaan
op die wisselaar wat voorl^e. Hierdie onre elmatige items word op re
ektiewe viniel geplaas en
uitgesny wat lei tot die vermorsing van stukkies viniel. Die fokus van hierdie tesis is om die
onre elmatige items op 'n optimale en tydige wyse vir gebruik in industrie, op die viniel te
plaas sodat die afval stukkies viniel geminimeer word. Die vinieldrukker, wat die onre elmatige
items sny uit die viniel, bestaan uit 'n vaste wydte en is slegs beperk in hoogte deur die viniel
self. Dus kan hierdie probleem beskryf word as 'n Twee-Dimensionele Onre elmatige Strookverpakkingsprobleem.
Hierdie onre elmatige items het slegs 'n paar moontlike hoogtes vir elke tipe
van onre elmatige item wat verpak word, wat dit moontlik maak om hierdie onre elmatige items
te verpak as 'n strook verpakkingsprobleem. Die items word met behulp van 'n gede nieerde
stel re els binne vlakke verpak asof hulle re elmatige items is. In hierdie tesis is verskeie verpakkingsalgoritmes
en beeldverwerkingsmetodes van die literatuur nagevors en gebruik om 'n
nuwe verpakkingsalgoritme vir hierdie spesi eke probleem te ontwikkel. Die nuut ontwikkelde algoritme
se prestasie is deur middel van verskeie normbepalingsvoorbeelde getoets. Sommige van
hierdie normbepalingsvoorbeelde is verkry van Kohler Signs self, terwyl ander lukraak gegenereer
is onder sekere voorwaardes. Hierdie normbepalingsvoorbeelde toon dat die nuut ontwikkelde
algoritme beter vaar as die beproefde tegnieke gebruik in industrie deur Kohler Signs vir beide
die minimering van vermorsde viniel sowel as die minimering van die algoritme se uitvoertyd.

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/96129
Date12 1900
CreatorsBossenger, Wayne
ContributorsNieuwoudt, Isabelle, Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Economics.
PublisherStellenbosch : Stellenbosch University
Source SetsSouth African National ETD Portal
Languageen_ZA
Detected LanguageUnknown
TypeThesis
Format84 p. : ill.
RightsStellenbosch University

Page generated in 0.0017 seconds