2D irregular strip packing at Kohler signs

[摘要] 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 wellas manufacture advertisement signs to be placed on vehicles. Road signs consist of steel sheetsthat are cut and bent to the appropriate size and frame, and an image design, which is cut fromreective 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 arecombined in a distinctive way, with the use of di erent coloured vinyl, they convey a message tothe road user which may be to yield for pedestrians crossing the street, or indicate to the roaduser the various highway exits that exist on the interchange ahead. These irregular items areplaced upon reective vinyl for cutting which results in vinyl o cuts that are wasted. The focusof this thesis is to minimise the waste incurred by placing these irregular items upon the vinylin an optimal and timely manner for industry use. The vinyl printer, which cuts the irregularitems out of the vinyl, consists of axed 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 packedwithin levels as though they are regular items with the assistance of a prede ned rule-set. Inthis thesis various packing algorithms and image processing methodologies from the literatureare researched and used to develop a new packing algorithm for this speci c problem. The newlydeveloped algorithm is put through various benchmarks to test its performance. Some of thesebenchmarks are procured from Kohler Signs themselves, whereas others are randomly generatedunder certain conditions. These benchmarks reveal that the newly developed algorithm performsbetter for both the minimisation of waste and the minimisation of algorithm running time thanthe tried and trusted techniques utilised in industry by Kohler Signs.

[发布机构] Stellenbosch University