Thesis (PhD (Logistics))--University of Stellenbosch, 2010. / ENGLISH ABSTRACT: Packing problems are common in industry and there is a large body of literature on the subject. Two packing problems are considered in this dissertation: the strip packing problem and the bin packing problem. The aim in both problems is to pack a speci ed set of small items, the dimensions of which are all known prior to packing (hence giving rise to an o ine problem), into larger objects, called bins. The strip packing problem requires packing these items into a single bin, one dimension of which is unbounded (the bin is therefore referred to as a strip). In two dimensions the width of the strip is typically speci ed and the aim is to pack all the items into the strip, without overlapping, so that the resulting packing height is a minimum. The bin packing problem, on the other hand, is the problem of packing the items into a speci ed set of bins (all of whose dimensions are bounded) so that the wasted space remaining in the bins (which contain items) is a minimum. The bins may all have the same dimensions (in which case the problem is known as the single bin size bin packing problem), or may have di erent dimensions, in which case the problem is called the multiple bin size bin packing problem (MBSBPP). In two dimensions the wasted space is the sum total of areas of the bins (containing items) not covered by items. Many solution methodologies have been developed for above-mentioned problems, but the scope of the solution methodologies considered in this dissertation is restricted to heuristics. Packing heuristics follow a xed set of rules to pack items in such a manner as to nd good, feasible (but not necessarily optimal) solutions to the strip and bin packing problems within as short a time span as possible. Three types of heuristics are considered in this dissertation: (i) those that pack items into levels (the heights of which are determined by the heights of the tallest items in these levels) in such a manner that all items are packed along the bottom of the level, (ii) those that pack items into levels in such a manner that items may be packed anywhere between the horizontal boundaries that de ne the levels, and (iii) those heuristics that do not restrict the packing of items to levels. These three classes of heuristics are known as level algorithms, pseudolevel algorithms and plane algorithms, respectively. A computational approach is adopted in this dissertation in order to evaluate the performances of 218 new heuristics for the strip packing problem in relation to 34 known heuristics from the literature with respect to a set of 1 170 benchmark problem instances. It is found that the new level-packing heuristics do not yield signi cantly better solutions than the known heuristics, but several of the newly proposed pseudolevel heuristics do yield signi cantly better results than the best of the known pseudolevel heuristics in terms of both packing densities achieved and computation times expended. During the evaluation of the plane algorithms two classes of heuristics were identi ed for packing problems, namely sorting-dependent and sortingindependent algorithms. Two new sorting techniques are proposed for the sorting-independent algorithms and one of them yields the best-performing heuristic overall. A new heuristic approach for the MBSBPP is also proposed, which may be combined with level and pseudolevel algorithms for the strip packing problem in order to nd solutions to the problem very rapidly. The best-performing plane-packing heuristic is modi ed to pack items into the largest bins rst, followed by an attempted repacking of the items in those bins into smaller bins with the aim of further minimising wasted space. It is found that the resulting plane-packing algorithm yields the best results in terms of time and packing density, but that the solution di erences between pseudolevel algorithms are not as marked for the MBSBPP as for the strip packing problem. / AFRIKAANSE OPSOMMING: Inpakkingsprobleme kom algemeen in die industrie voor en daar is 'n aansienlike volume literatuur oor hierdie onderwerp. Twee inpakkingsprobleme word in hierdie proefskrif oorweeg, naamlik die strook-inpakkingsprobleem en die houer-inpakkingsprobleem. In beide probleme is die doel om 'n gespesi seerde versameling klein voorwerpe, waarvan die dimensies almal voordat inpakking plaasvind, bekend is (en die probleem dus 'n sogenaamde a yn-probleem is), in een of meer groter houers te pak. In die strook-inpakkingsprobleem word hierdie voorwerpe in een houer, waarvan een dimensie onbegrens is, ingepak (hierdie houer word dus 'n strook genoem). In twee dimensies word die wydte van die strook gewoonlik gespesi seer en is die doel om al die voorwerpe sonder oorvleueling op s o 'n manier in die strook te pak dat die totale inpakkingshoogte geminineer word. In die houer-inpakkingsprobleem, daarenteen, is die doel om die voorwerpe op s o 'n manier in 'n gespesi seerde aantal houers (waarvan al die dimensies begrens is) te pak dat die vermorste of oorblywende ruimte in die houers (wat wel voorwerpe bevat) 'n minimum is. Die houers mag almal dieselfde dimensies h^e (in welke geval die probleem as die enkelgrootte houer-inpakkingsprobleem bekend staan), of mag verskillende dimensies h^e (in welke geval die probleem as die veelvuldige-grootte houer-inpakkingsprobleem bekend staan, afgekort as VGHIP). In twee dimensies word die vermorste ruimte geneem as die somtotaal van daardie deelareas van die houers (wat wel voorwerpe bevat) waar daar geen voorwerpe geplaas word nie. Verskeie oplossingsmetodologie e is al vir die bogenoemde twee inpakkingsprobleme ontwikkel, maar die bestek van die metodologie e wat in hierdie proefskrif oorweeg word, word beperk tot heuristieke. 'n Inpakkingsheuristiek volg 'n vaste stel re els waarvolgens voorwerpe in houers gepak word om so spoedig moontlik goeie, toelaatbare (maar nie noodwendig optimale) oplossings tot die strook-inpakkingsprobleem en die houer-inpakkingsprobleem te vind. Drie tipes inpakkingsheuristieke word in hierdie proefskrif oorweeg, naamlik (i) heuristieke wat voorwerpe langs die onderste randte van horisontale vlakke in die houers pak (die hoogtes van hierdie vlakke word bepaal deur die hoogtes van die hoogste item in elke vlak), (ii) heuristieke wat voorwerpe op enige plek binne horisontale stroke in die houers pak, en (iii) heuristieke waar inpakking nie volgens horisontale vlakke of stroke beperk word nie. Hierdie drie klasse heuristieke staan onderskeidelik as vlakalgoritmes, pseudo-vlakalgoritmes en platvlakalgoritmes bekend. 'n Berekeningsbenadering word in hierdie proefskrif gevolg deur die werkverrigting van die 218 nuwe heuristieke vir die strook-inpakkingsprobleem met die werkverrigting van 34 bekende heuristieke uit die literatuur te vergelyk, deur al die heuristieke op 1 170 toetsprobleme toe te pas. Daar word bevind dat die nuwe vlakalgoritmes nie 'n noemenswaardige verbetering in oplossingskwaliteit in vergeleke met soortgelyke bestaande algoritmes in die literatuur lewer nie, maar dat verskeie nuwe pseudo-vlakalgoritmes wel noemenswaardige verbeteringe in terme van beide inpakkingsdigthede en oplossingstye in vergeleke met die beste bestaande algoritmes in die literatuur lewer. Assessering van die platvlakalgoritmes het gelei tot die identi kasie van twee deelklasse van algoritmes, naamlik sorteringsafhanklike- en sorteringsonafhanklike algoritmes. Twee nuwe sorteringstegnieke word ook vir die deelklas van sorteringsonafhanklike algoritmes voorgestel, en een van hulle lewer die algeheel beste inpakkingsheursitiek. 'n Nuwe heuristiese benadering word ook vir die VGHIP ontwikkel. Hierdie benadering kan met vlak- of pseudo-vlakalgoritmes vir die strook-inpakkingsprobleem gekombineer word om baie vinnig oplossings vir die VGHIP te vind. Die beste platvlakheuristiek vir die strookinpakkingsprobleem word ook aangepas om voorwerpe eers in die grootste houers te pak, en daarna in kleiner houers te herpak met die doel om vermorste ruimte verder te minimeer. Daar word bevind dat die resulterende platvlakalgoritme die beste resultate in terme van beide inpakkingsdigtheid en oplossingstyd lewer, maar dat oplossingsverskille tussen die pseudovlakalgoritmes nie so opmerklik vir die VGHIP is as wat die geval met die strookinpakkingsprobleem was nie.

Dissertation (PhD)--Stellenbosch, 2004. / ENGLISH ABSTRACT: The dissertation reflects the research done on the design principles and success factors for the operation of cross dock facilities in grocery and retail supply chains. The cross dock is a particular facility in the supply chain where goods are received from suppliers, sorted without storage of the goods, and then efficiently moved to downstream customers. Cross docks are not a new operation. However, the use in high volume grocery and retail operational capabilities is poorly understood and is not uniquely defined. The problem is that cross docks are often seen as extensions of warehouses. The same personnel, systems and processes are applied and the efficiency potential of the cross dock is not achieved. Warehouses are orientated towards storing the full range of product and allowing the pick to be done from this storage buffer to provide any or all of these products to a customer. Cross docks will only handle products that are used in larger quantities and that are sent to most, if not all, the customers. The cross dock is therefore distinct and very different from the traditional warehouse. The published research tends to focus on the technical aspects of the cross dock layout. This research is primarily in the scheduling of the trucks into the yard of the facility; the allocation of trucks to specific doors of the facility; and the allocation of doors to receiving and despatch functions within the facility. Very little information or research reflects the design principles and success factors for the cross dock and its supply chain. The only classification of the cross dock in the literature is whether the barcode is added to the item before or after receipt at the cross dock. For this research work a literature survey was conducted and five major operations were reviewed, in South Africa and the USA. The research empirically drew logical conclusions, which were tested in the operations and found to be correct. This allowed the design principles and success factors to be determined for a successful cross dock. The research extends the knowledge of the cross dock operation and design: - • A new classification for the feasible types of cross docks in the supply chain was developed. Three factors are shown to be of primary importance: - o Where in the supply chain the identification of specific items for a customer is done; o Where the sort is done for the items to be delivered to a customer; and o Whether the supplier is providing one product or multiple products to the sort. From these three factors, eight potential classifications could be defined. However, only three practical types of cross dock can be determined from these eight alternatives. These are named in this research as Cross Dock Managed Load (CML); Joint Managed Load (JML); and the Supplier Managed Load (SML). The cross dock is far more effective than the warehouse when the total work (excluding inventory) is considered. The earlier in the supply chain the product is identified for the use of the entire downstream supply chain, the more effective will be the total supply chain. Thus the greatest supply chain effectiveness possible is with the SML, then the JML and finally the CML. • The operation of a cross dock is very similar to a continuous manufacturing process. There is no buffer of stock to decouple the inbound and outbound processes, and the operation takes place in a restricted area. However, in the retail chain, the workload alters with different orders and different days. Daily load differences vary by as much as 90%. This results in vastly different workloads and variations of throughput. This is similar to a batch operation with highly variable workloads between batches. The literature recommends the use of Just in Time (JIT) practice for cross docks. This is inappropriate as its primary requirements are continuous full volume operation and continuous small improvements to achieve a balanced operation. The most appropriate method of process improvement is the Theory of Constraints (TO C) and not JlT. • The management must have a detailed, disciplined approach. This implies standardised methods of operation, and a high degree of training. Equally there is the requirement for a special type of personnel to operate the cross dock. These operating personnel must be able to operate with precision (i.e. very low error rates) and be able to maintain this capability for continuous periods. • The systems required for a successful operation must include the capabilities of Yard Management, WMS for cross docking, Order Management with Advanced Shipping Notice (ASN) capability and Track and Trace across the supply chain. The items need to be identified by a barcode. The information required on the barcode will be determined by. the information systems capability of the least advanced service provider in the supply chain. If this service provider can receive and transmit all the data required for the supply chain from and to the other members, then the barcode need only be an identification number of the specific item. The data pertaining to the items is then passed from system to system in the supply chain. If data movement is not possible between all the parties in the entire supply chain, then the barcode must contain the information that will identify the item, the origin and the final delivery destination. If the items are delivered as part of a consignment, a further quantum of information is required to identify the total number of items in the consignment and the specific item within the consignment. • The research shows that the overall capability of the cross dock or its maximum capacity is the combination of the capability of the personnel and the cross dock design. Restrictions on either the personnel capability or the design of the cross dock, or both, severely reduces the effectiveness of the cross dock. • The previous research on the sequence of allocation of trucks to specific doors within the cross dock can be enhanced with a new sequencing method. The new method allocates the transport, in sequence of arrival, to the open door that either numrruses the walk distance in the facility; or maximises the completion of the consignments in order to minimise the area required to build the consignments; or a combination of both. The choice of these will be determined by the constraints imposed by the design of the building. This is an important extension as this ties the supply chain into the cross dock operation, rather than looking at the cross dock in isolation as has been done in this previous research. • The factors that influence the design of a cross dock as to its size, shape, number of doors, and the specifically required additional areas, is defined in detail. The principles of these factors and their inter-relationships and dependencies are used in a detailed design for a cross dock. The detailed design process is set out from data analysis through to the actual size calculations and layouts. Measurements of walk distance and sort movement are used to determine the most effective design. The design is shown to be considerably more effective than the older designs. This work has significantly extended the research on the design principles and success factors for implementation of cross docks in retail supply chains. The research derives a unique new classification for cross docks. An improvement is made to existing research on the allocation of the transport to particular doors in the cross dock. The operation, management and personnel are shown to require specific characteristics. The information systems required for effective cross docks is determined and defined. The identification of the individual items by barcode and the information required within the barcode depending on the information sophistication of the service providers in the supply chain is defined. A detail process to design a cross dock is evolved, with the full knowledge of the factors that must be considered and their interrelationships. Measurements to determine the effectiveness of the design are used to choose the most appropriate design. All these are then synthesised into a new design, which is far more effective than any of the other designs researched. The design process will produce a very effective cross dock as has been demonstrated with a new facility. / AFRIKAANSE OPSOMMING: geen opsomming

Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The policing and monitoring of South Africa's coastline and economic exclusion zone is made di cult not only by the size of the area of interest, but also by the limited resources available for maritime detection and policing. As a consequence, illegal activities, such as smuggling, poaching and illegal border crossings, are often conducted with impunity. Conventional approaches to monitoring coastal areas, such as the use of patrol boats, port inspections and aircraft surveillance, may be augmented by advances in technology that are steadily contributing vast amounts of data related to maritime activity. For example, various South African agencies collect auto- matic identi cation system and vessel monitoring system transmissions, and gather additional kinematic data of maritime vessels through a number of strategically placed coastal radars. A command and control centre for actively monitoring these data (outside of the intelligence community) was established by the South African Navy in 2014. Such centres provide surveillance operators with a real-time picture of a maritime region of interest from which they can identify relevant facts of interest through a reliance on experience and domain knowledge. The e ectiveness of this process may, however, be undermined by the vast quantities of data typically under consideration, by the di culty of identifying long-term trends in vessel kinematic behaviour and by the possibility of operator fatigue brought on by the relatively low incidence levels of activities of interest. E ective decision support tools may play a valuable role in this context by the automatic processing of these vast collections of data, by the identi cation of concepts of interest and by the prediction of future occurrences of interest. It is, however, essential that such tools should be exible enough to adapt to changes in typical vessel behaviour over time and that they should be capable of integrating new trends and new types of behaviours. Various approaches to maritime surveillance are investigated in this dissertation from the perspectives of threat detection and anomaly identi cation, with particular emphasis on a systems approach to decision support. A decision support system framework that utilises rule-based and data-driven mechanisms is proposed as a means to separate the interesting from the uninteresting and to provide early warnings of potentially threatening maritime vessel behaviour to operators. This system framework is primarily concerned with kinematic data and is restricted to the identi cation of certain types of activities. Successful classi cation and, ultimately, timely prediction of potentially threatening behaviour would allow for e ective policing by providing early warning to relevant entities, thus potentially leading to more e ective use of available policing resources. / AFRIKAANSE OPSOMMING: Die patrollering en monitering van die Suid-Afrikaanse kusgebied en gepaardgaande ekonomiese eksklusiewe zone word bemoeilik deur die grootte van die tersprake area en die beperkte hulpbronne wat vir patrollie-doeleindes aangewend kan word. Gevolglik gaan onwettige aktiwiteite, soos smokkelary, stroping en onwettige immigrasie dikwels ongestraf. Konvensionele benaderings tot die monitering van kusgebiede, soos die aanwending van patrolliebote, die uitvoer van hawe-inspeksies en gere elde lugpatrollies, kan aangevul word deur tegnologiese vooruitgang wat voortdurend tot groot hoeveelhede data oor maritieme aktiwiteit bydra. Verskeie Suid- Afrikaanse agentskappe ontvang byvoorbeeld outomatiese identi kasiestelsel en vaartuigmoni- teringstelsel uitsendings, en samel ook addisionele kinematiese data oor maritieme vaartuie deur middel van strategies-geplaasde kusradars in. 'n Bevel-en-beheersentrum wat hierdie inligting (buite die intelligensiegemeenskap) aktief ontleed, is in 2014 deur die Suid-Afrikaanse Vloot tot stand gebring. Sulke sentra verskaf 'n intydse blik oor die maritieme gebied onder beskouing aan operateurs wat dan, gebaseer op hulle ervaring en omgewingskennis, relevante inligting oor vaartuie kan a ei. Die doeltre ende uitvoering van hierdie proses kan egter ondermyn word deur die tipiese groot hoeveelhede data, die moeilikheidsgraad van die identi kasie van langtermyn tendense in die kinematiese gedrag van vaartuie om die kus en die moontlikheid van operateur-uitputting as gevolg van lang periodes van relatiewe oninteressante vaartuiggedrag. Doeltre ende besluitsteunhulpmiddels kan 'n waardevolle bydrae in hierdie konteks maak deur die ge-outomatiseerde prosessering van hierdie groot hoeveelhede data, die identi kasie van interessante vaartuiggedrag en die voorspelling van toekomstige relevante insidente. Dit is egter noodsaaklik dat sulke hulpmiddels buigsaam genoeg moet wees om te kan aanpas by veranderings in tipiese maritieme aktiwiteit oor tyd en dat nuwe tendense en tipes aktiwiteite geakkommodeer kan word. Verskeie benaderings tot maritieme oorsig word in hierdie proefskrif vanuit die perspektiewe van die bespeuring van bedreigings en die opsporing van vreemde verskynsels ondersoek, met 'n spesi eke fokus op 'n stelselbenadering tot besluitsteun. 'n Besluitsteun stelselraamwerk wat berus op re el-gebaseerde en data-aangedrewe meganismes word as 'n hulpmiddel voorgestel waarmee interessante maritieme gedrag van oninteressante gedrag onderskei kan word om sodoende 'n vroe e waarskuwing aan operateurs met betrekking tot moontlike bedreigende maritieme aktiwiteite te kan rig. Die werking van hierdie stelselraamwerk berus hoofsaaklik op die gebruik van kinematiese vaartuigdata en is beperk tot die naspeuring van sekere soorte bedreigende gedrag. Die suksesvolle klassi kasie en tydige voorspelling van potensi ele bedreigende maritieme gedrag behoort doeltre ende kusmonitering en verbeterde aanwending van die beperkte, gepaardgaande hulpbronne deur relevante kusagentskappe moontlik te maak.

Thesis (MSc)--Stellenbosch University, 2011. / ENGLISH ABSTRACT: As the world-wide consumption of electricity continually increases, more and more pressure is put on the capabilities of power generating systems to maintain their levels of power provision. The electricity utility companies operating these power systems are faced with numerous challenges with respect to ensuring reliable electricity supply at cost-e ective rates. One of these challenges concerns the planned preventative maintenance of a utility's power generating units. The generator maintenance scheduling (GMS) problem refers to the problem of nding a schedule for the planned maintenance outages of generating units in a power system (i.e. determining a list of dates corresponding to the times when every unit is to be shut down so as to undergo maintenance). This is typically a large combinatorial optimisation problem, subjected to a number of power system constraints, and is usually difficult to solve. A mixed-integer programming model is presented for the GMS problem, incorporating constraints on maintenance windows, the meeting of load demand together with a safety margin, the availability of maintenance crew and general exclusion constraints. The GMS problem is modelled by adopting a reliability optimality criterion, the goal of which is to level the reserve capacity. Three objective functions are presented which may achieve this reliability goal; these objective functions are respectively quadratic, nonlinear and linear in nature. Three GMS benchmark test systems (of which one is newly created) are modelled accordingly, but prove to be too time consuming to solve exactly by means of an o -the-shelf software package. Therefore, a metaheuristic solution approach (a simulated annealing (SA) algorithm) is used to solve the GMS problem approximately. A new ejection chain neighbourhood move operator in the context of GMS is introduced into the SA algorithm, along with a local search heuristic addition to the algorithm, which results in hybridisations of the SA algorithm. Extensive experiments are performed on di erent cooling schedules within the SA algorithm, on the classical and ejection chain neighbourhood move operators, and on the modi cations to the SA algorithm by the introduction of the local search heuristic. Conclusions are drawn with respect to the e ectiveness of each variation on the SA algorithm. The best solutions obtained during the experiments for each benchmark test case are reported. It is found that the SA algorithm, with ejection chain neighbourhood move operator and a local search heuristic hybridisation, achieves very good solutions to all instances of the GMS problem. The hybridised simulated annealing algorithm is implemented in a computerised decision support system (DSS), which is capable of solving any GMS problem instance conforming to the general formulation described above. The DSS is found to determine good maintenance schedules when utilised to solve a realistic case study within the context of the South African power system. A best schedule attaining an objective function value within 6% of a theoretical lowerbound, is thus produced. / AFRIKAANSE OPSOMMING: Met die wêreldwye elektrisiteitsverbruik wat voortdurend aan die toeneem is, word daar al hoe meer druk geplaas op die vermoë van kragstelsels om aan kragvoorsieningsaanvraag te voldoen. Nutsmaatskappye wat elektrisiteit opwek, word deur talle uitdagings met betrekking tot betroubare elektrisiteitsverskaffing teen koste-e ektiewe tariewe in die gesig gestaar. Een van hierdie uitdagings het te make met die beplande, voorkomende instandhouding van 'n nutsmaatskappy se kragopwekkingseenhede. Die generator-instandhoudingskeduleringsprobleem (GISP) verwys na die probleem waarin 'n skedule vir die beplande instandhouding van kragopwekkingseenhede binne 'n kragstelsel gevind moet word ('n lys van datums moet tipies gevind word wat ooreenstem met die tye wanneer elke kragopwekkingseenheid afgeskakel moet word om instandhoudingswerk te ondergaan). Hierdie probleem is tipies 'n groot kombinatoriese optimeringsprobleem, onderworpe aan 'n aantal beperkings van die kragstelsel, en is gewoonlik moeilik om op te los. 'n Gemengde, heeltallige programmeringsmodel vir die GISP word geformuleer. Die beperkings waaruit die formulering bestaan, sluit in: venstertydperke vir instandhouding, bevrediging van die vraag na elektrisiteit tesame met 'n veiligheidsgrens, die beskikbaarheid van instandhoudingspersoneel en algemene uitsluitingsbeperkings. Die GISP-model neem as optimaliteitskriterium betroubaarheid en het ten doel om die reserwekrag wat gedurende elke tydperk beskikbaar is, gelyk te maak. Drie doelfunksies word gebruik om laasgenoemde doel te bereik (naamlik doelfunksies wat onderskeidelik kwadraties, nie-lineêr en lineêr van aard is). Drie GISP-maatstaftoetsstelsels (waarvan een nuut geskep is) is dienooreenkomstig gemodelleer, maar dit blyk uit die oplossingstye dat daar onprakties lank gewag sal moet word om eksakte oplossings deur middel van kommersiële programmatuur vir hierdie stelsels te kry. Gevolglik word 'n metaheuristiese oplossingsbenadering ('n gesimuleerde temperingsalgoritme (GTA)) gevolg om die GISP benaderd op te los. 'n Nuwe uitwerpingsketting-skuifoperator word in die konteks van GISP in die GTA gebruik. Verder word 'n lokale soekheuristiek met die GTA vermeng om 'n basteralgoritme te vorm. Uitgebreide eksperimente word uitgevoer op verskeie afkoelskedules binne die GTA, op die klassieke en uitwerpingsketting-skuifoperators en op die verbasterings van die GTA meegebring deur die lokale soekheuristiek. Gevolgtrekkings word oor elke variasie van die GTA se e ektiwiteit gemaak. Die beste oplossings vir elke toetsstelsel wat gedurende die eksperimente verkry is, word gerapporteer. Daar word bevind dat die GTA met uitwerpingsketting-skuifoperator en lokale soekheuristiek-verbastering baie goeie oplossings vir die GISP lewer. Die verbasterde GTA word in 'n gerekenariseerde besluitsteunstelsel (BSS) geïmplementeer wat 'n gebruiker in staat stel om enige GISP van die vorm soos in die wiskundige programmeringsmodel hierbo beskryf, op te los. Daar word bevind dat die BSS goeie skedules lewer wanneer dit gebruik word om 'n realistiese gevallestudie binne die konteks van die Suid-Afrikaanse kragstelsel, op te los. 'n Beste skedule met 'n doelfunksiewaarde wat binne 6% vanaf 'n teoretiese ondergrens is, word ondermeer bepaal.

Thesis (MSc (Logistics)--University of Stellenbosch, 2007. / There exists, for any connected graph G, a minimum set of vertices that, when removed, disconnects G. Such a set of vertices is known as a minimum cut-set, the cardinality of which is known as the connectivity number k(G) of G. A connectivity preserving [connectivity reducing, respectively] spanning subgraph G0 ? G may be constructed by removing certain edges of G in such a way that k(G0) = k(G) [k(G0) < k(G), respectively]. The problem of constructing such a connectivity preserving or reducing spanning subgraph of minimum weight is known to be NP–complete. This thesis contains a summary of the most recent results (as in 2006) from a comprehensive survey of literature on topics related to the connectivity of graphs. Secondly, the computational problems of constructing a minimum weight connectivity preserving or connectivity reducing spanning subgraph for a given graph G are considered in this thesis. In particular, three algorithms are developed for constructing such spanning subgraphs. The theoretical basis for each algorithm is established and discussed in detail. The practicality of the algorithms are compared in terms of their worst-case running times as well as their solution qualities. The fastest of these three algorithms has a worst-case running time that compares favourably with the fastest algorithm in the literature. Finally, a computerised decision support system, called Connectivity Algorithms, is developed which is capable of implementing the three algorithms described above for a user-specified input graph.

Thesis (MComm)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: In a ground-based air defense (GBAD) military environment, defended assets on the ground require protection from enemy aircraft entering the defended airspace. These aircraft are detected by means of a network of sensors and protection is afforded by means of a pre-deployment of various ground-based weapon systems. A fire control officer is responsible for deciding upon an assignment of weapon systems to those aircraft classified as threats. The problem is therefore to find the best set of weapon systems to assign to the threats, based on some pre-specified criterion or set of criteria. This problem is known as the weapon assignment problem. The conditions under which the fire control officer has to operate are typically extremely stressful. A lack of time is a severely constraining factor, and the fire control officer has to propose an assignment of weapon systems to threats based on his limited knowledge and intuition, with little time for analysis and no room for error. To aid the fire control officer in this difficult decision, a computerised threat evaluation and weapon assignment (TEWA) decision support system is typically employed. In such a decision support system a threat evaluation subsystem is responsible for classifying aircraft in the defended airspace as threats and prioritising them with respect to elimination, whereas a weapon assignment subsystem is responsible for proposing weapon assignments to engage these threats. The aim in this thesis is to model the weapon assignment problem as a multiobjective decision problem. A list of relevant objectives is extracted by means of feedback received from a weapon assignment questionnaire which was completed by a number of military experts. By using two of these objectives, namely the cost of assigning weapon systems and the accumulated single shot hit probability, for illustrative purposes, a bi-objective weapon assignment model is derived and solved by means of three multiobjective optimisation methodologies from the literature in the context of a simulated, but realistic, GBAD scenario. The analytic hierarchy process (AHP) is implemented by means of assessments carried out in conjunction with a military expert. The assignment of weapon systems to threats is achieved by means of a greedy assignment heuristic and an AHP assignment model. Both these methods provide plausible results in the form of high quality assignments achieving an acceptable tradeoff between the two decision objectives. However, a disadvantage of the AHP approach is that it is inflexible in the sense that a large portion of its pre-assessments have to be reiterated if the set of weapon systems and/or threats is adapted or updated. A bi-objective additive utility function solution approach to the weapon assignment problem is also developed as a result of various assessments having been carried out in conjunction with a military expert. The assignment of weapon systems to threats is again achieved by means of a greedy assignment heuristic and a utility assignment model. Both these methods again provide high quality assignments of weapon systems to threats, achieving an acceptable trade-off between the two decision objectives. However, a disadvantage of the utility function approach is that if additional weapon systems are added to the current set of weapon systems, which achieve objective function values outside the current ranges of the values employed, new utility functions have to be determined for the relevant objective function. Moreover, both the AHP and utility function approaches are also constrained by generating only one solution at a time. A final solution approach considered is the implementation of a multiobjective evolutionary metaheuristic, known as the Nondominated Sorting Genetic Algorithm II (NSGA II). This approach provides very promising results with respect to high quality assignments of weapon systems to threats. It is also flexible in the sense that additional weapon systems and threats may be added to the current sets without the need of considerable additional computations or significant model changes. A further advantage of this approach is that it is able to provide an entire front of approximately pareto optimal solutions to the fire control officer. / AFRIKAANSE OPSOMMING: In ’n militêre grond-gebaseerde lugafweeromgewing vereis bates op die grond beskerming teen vyandelike vliegtuie wat die beskermde lugruim binnedring. Hierdie vliegtuie word deur middel van ’n netwerk van sensors waargeneem en deur middel van ’n ontplooing van ’n verskeidenheid grond-gebaseerde wapenstelsels afgeweer. ’n Afvuur-beheer operateur is verantwoordelik vir die besluit om wapenstelsels aan vliegtuie wat as bedreigings geklassifiseer is, toe te wys. Die onderliggende probleem is dus om die beste stel wapens, volgens ’n voorafbepaalde kriterium of ’n stel kriteria, aan die bedreigings toe te wys. Hierdie probleem staan as die wapentoewysingsprobleem bekend. Die toestande waaronder die afvuur-beheer operateur besluite ten opsigte van wapentoewysings maak, is besonder stresvol. ’n Gebrek aan tyd is ’n uiters beperkende faktor, en die afvuurbeheer operateur moet gevolglik binne ’n tydspan wat weinige analise en geen ruimte vir foute toelaat, wapentoewysings volgens sy beperkte kennis en intuïsie maak. ’n Gerekenariseerde bedreigingsafskatting-en-wapentoekenningstelsel kan gebruik word om die operateur met besluitsteun te bedien. In sò ’n besluitsteunstelsel is ’n bedreigingsafskattingdeelstelsel verantwoordelik om vliegtuie wat die beskermde lugruim binnedring as bedreigings of andersins te klassifiseer en ten opsigte van eliminasie te prioritiseer, terwyl ’n wapentoewyingsdeelstelsel verantwoordelik is om wapentoewysings aan die bedreigings voor te stel. Die hoofdoel in hierdie tesis is om die wapentoewysingsprobleem as ’n multikriteria-besluitnemingsprobleem te modelleer. ’n Lys van relevante doelwitte is met behulp van ’n wapentoewysingsvraelys verkry wat aan militêre kenners vir voltooing uitgestuur is. Twee van hierdie doelwitte, naamlik toewysingskoste en geakkumuleerde enkelskoot-trefwaarskynlikheid, is vir illustratiewe doeleindes gebruik om ’n twee-doelwit wapentoewysingsprobleem te formuleer wat met behulp van drie multikriteria-besluitnemingsmetodologië uit die literatuur in die konteks van ’n realistiese, gesimuleerde grond-gebaseerde lugafweerscenario opgelos word. Die analitiese hiërargiese proses (AHP) is met behulp van assesserings in samewerking met ’n militêre kenner geïmplementeer. Die toewysing van wapenstelsels is met behulp van ’n gulsige toewysingsheuristiek asook aan die hand van ’n AHP-toewysingsmodel bepaal. Beide hierdie metodes is in staat om resultate van hoë gehalte te behaal wat ’n aanvaarbare afruiling tussen die twee doelwitte verteenwoordig. ’n Nadeel van die AHP is egter dat dit onbuigsaam is in die sin dat ’n groot hoeveelheid vooraf-assesserings herhaal moet word indien meer wapenstelsels en/of bedreigings by die huidige sisteem gevoeg word. ’n Twee-doelwit additiewe nutsfunksiebenadering tot die wapentoewysingsprobleem is ook met behulp van velerlei assesserings in samewerking met ’n militêre kenner ontwikkel. Die toewysings is weereens met behulp van ’n gulsige wapentoewysingsheuristiek asook ’n nutstoewysingsmodel bepaal. Beide hierdie metodes is ook in staat om resultate van hoë gehalte te behaal wat ’n aanvaarbare afruiling tussen die twee doelwitte verteenwoordig. ’n Nadeel van die nutsfunksiebenadering is egter dat indien addisionele wapenstelsels by die huidige stel wapenstelsels gevoeg word, en indien die waardes van hierdie addisionele wapenstelsels buite die grense van die doelfunksiewaardes van die huidige wapenstelsels val, daar ’n nuwe nutsfunksie vir die relevante doelwit van voor af bereken moet word. Beide die AHP- en die nutsfunksiebenaderings is verder tot die lewering van slegs een oplossing op ’n slag beperk. Laastens is ’n multikriteria evolusionêre metaheuristiek (die NSGA II) geïmplementeer wat ook goeie resultate in terme van hoë-gehalte toewysings van wapenstelsels aan bedreigings lewer. Die voordeel van hierdie benadering is dat dit buigsaam is in die sin dat die getal wapenstelsels en bedreigings in die huidige sisteem aangepas kan word sonder om noemenswaardig meer berekeninge of groot modelveranderinge teweeg te bring. ’n Verdere voordeel is dat die metaheuristiese benadering daartoe in staat is om ’n front van benaderde pareto-optimale oplossings gelyktydig te lewer.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Order picking is the most important activity in distribution centres. It involves the process of retrieving products from storage in response to a speci c customer request. The order picking system in a distribution centre used by Pep Stores Ltd. (Pep), located in Durban, South Africa, is considered. The order picking system in Pep utilises picking lines. The system requires that the pickers move in a clockwise direction around the picking line. The planning of picking lines may be divided into three tiers of decisions. The rst tier determines which Stock Keeping Units (SKUs) should be allocated to which picking line and is known as the SKU to Picking Line Assignment Problem (SPLAP). The second tier, the SKU Location Problem (SLP), considers the positioning of the various SKUs in a picking line. The nal tier considers the sequencing of the orders for pickers within a picking line and is referred to as the Order Sequencing Problem (OSP). Collectively, these three tiers aim to achieve the objective of picking all the SKUs for all the orders in the shortest possible time. The decisions associated with each tier are made sequentially during the planning of a picking line. Each problem therefore relies on the information generated by its predecessing tier(s). Initially the OSP is addressed. A number of heuristic and metaheuristic approaches are presented, together with an exact formulation to solve this tier. The size of the problem is reduced by using a relaxation of the problem that may be solved exactly. A number of greedy tour construction heuristics, a scope and ranking algorithm, methods based on awarding starting locations with respect to preference ratios and a modi ed assignment approach was used to solve the OSP. Furthermore, a tabu search, simulated annealing, genetic algorithm and a generalised extremal optimisation approach are used to solve the OSP. The solution quality and computational times of all the approaches are compared for the data provided by Pep, with the generalised extremal optimisation approach delivering the best solution quality. Two methods from the literature was used to model the SLP, whereafter an ant colony system was used to maximise the number of orders in common between adjacent SKUs. A number of agglomerative clustering algorithms were used from which dendrograms could be constructed. Two novel heuristic clustering algorithms were considered. The rst heuristic calculates a distance between two clusters as the set of orders that have to collect all the SKUs in both clusters, whereas the second method is based upon the frequency of SKUs within a cluster. Little or no improvement was achieved in most cases. The SPLAP was introduced by means of a number of possibilities of how to formulate objectives. A possible exact formulation is presented, followed by a nearest neighbour search, which was initially used to construct new picking lines based on all data sets. A di erent approach was then taken by means of a tabu search where the waves of two or three picking lines were altered. Signi cant savings may be incurred for large data sets. / AFRIKAANSE OPSOMMING: Die opmaak van bestellings is die belangrikste aktiwiteit in 'n distribusiesentrum. Dit behels dat geskikte hoeveelhede produkte uit stoorplekke opgespoor en herpak moet word om aan kleinhandeltakke gestuur te word. Die bedrywighede binne een van Pep Stores Ltd. (Pep) se distribusiesentrums in Durban, Suid-Afrika, word beskou. Die sisteem vereis dat die werkers in 'n kloksgewyse rigting om 'n uitsoeklyn beweeg. Die beplanning van die uitsoeklyne kan verdeel word in drie besluite/probleme. Die eerste besluit is watter voorraadeenhede (VEs) toegewys moet word aan watter uitsoeklyn. Die tweede besluit is in watter vakkies in die uitsoeklyn die VEs geplaas moet word, en word die VE-plasings probleem (VLP) genoem. Die nale besluit is in watter volgorde bestellings opgemaak moet word in 'n uitsoeklyn, en staan bekend as die volgorde-van-bestellings-probleem (VBP). Die doel van al drie hierdie probleme is om al die bestellings in 'n uitsoeklyn in die kortste moontlike tyd af te handel. Die besluite wat verband hou met elke vlak van besluit word opeenvolgend gedoen tydens die beplanning van 'n uitsoeklyn. Die oplossing van elke subprobleem berus op die inligting van die voorafgaande probleme. Aanvanlik word die VBP beskou. 'n Aantal heuristiese en metaheuristiese benaderings word aangebied saam met 'n eksakte formulering om die derde vlak op te los. Die grootte van die probleem is verminder deur die gebruik van 'n verslapping van 'n eksakte formulering. 'n Aantal toerkonstruksie heuristieke, 'n omvang en rangorde algoritme, metodes wat gebaseer is op die toekenning van beginpunte met betrekking tot voorkeurverhoudings en 'n veralgemeende toewysingsprobleem is gebruik om die VBP op te los. 'n Tabu-soektog, gesimuleerde tempering, genetiese algoritme en 'n veralgemeende-ekstreme-optimering-benadering word ook gebruik om die VBP op te los. Die oplossingsgehalte en berekeningstye van al die benaderings word vergelyk vir werklike data wat verskaf is deur Pep. Die veralgemeende-ekstreme-optimering-benadering lewer die beste oplossingsgehalte. Twee metodes uit die literatuur is gebruik om die VLP te modelleer, waarna 'n mier kolonie stelsel gebruik word om die aantal bestellings wat aangrensende VEs in gemeen het te maksimeer. 'n Aantal groeperingsalgoritmes word gebruik wat dendrogramme kan lewer. Twee heuristiese groeperingsalgoritmes word oorweeg. Die eerste heuristiek bereken die afstand tussen twee groepe as die aantal bestellings wat al die VEs in beide groepe moet versamel, terwyl die tweede metode gebaseer is op die frekwensie van VEs binne 'n groep. Min of geen verbeterings is in die meeste gevalle gevind. Die eerste besluit word bekend gestel na aanleiding van 'n aantal moontlike maniere om die doelwitte te formuleer. 'n Moontlike eksakte formulering word aangebied. 'n Alternatiewe benadering is geneem deur middel van 'n tabu-soektog waar die golwe van twee of drie uitsoeklyne gewysig word. Beduidende besparings word gerealiseer vir groot datastelle.

ENGLISH ABSTRACT: The main aim in blending problems is to determine the best blend of available ingredients to form a certain quantity of product(s). This product should adhere to strict speci cations. In this study the best blend means the least-cost blend of ingredients (input) required to meet a minimum level of product (output) speci cations. The most prevalent tools to solve blending problems in the industry are by means of spreadsheets, simulators and mathematical programming. While there may be considerable bene t in using these types of tools to identify potential opportunities and infeasibilities, there is a potentially even greater bene t in searching automitically for alternative solutions that are more economical and e cient. Heuristics and metaheuristics are presented as useful alternative solution approaches. In this thesis di erent metaheuristic techniques are developed and applied to three typical blending problems of varied size taken from the petrochemical industry. a fourth instance of real life size is also introduced. Heuristics are developed intuitively, while metaheuristics are adopted from the literature. Random search techniques, such as blind random search and local random search, deliver fair results. Within the class of genetic algorithms the best results for all three problems were obtained using ranked tness assignment with tournament selection of individuals. Good results are also obtained by means of tabu search approaches - even considering the continuous nature of these problems. A simulated annealing approach also yielded fair results. A comparison of the results of the di erent approaches shows that the tabu search technique delivers the best result with respect to solution quality and execution time for all three the problems under consideration. Simulated annealing, however, delivers the best result with respect to solution quality and execution time for the introduced real life size problem. / AFRIKAANSE OPSOMMING: Die hoofdoelwit met die oplos van mengprobleme is om die beste mengsel van beskikbare bestandele te bepaal om 'n sekere hoeveelheid produk(te) te vervaardig. Die produk moet aan streng vereistes voldoen. Die beste kombinasie is die goedkoopste kombinasie van bestandele (toevoer) wat aan die minimum produkvereistes (afvoer) voldoen. Die algemeenste benaderings waarmee mengprobleme in die industrie opgelos word, is met behulp van sigblaaie, simulasies en wiskundige programmering. Hierdie metodes is baie nuttig om belowende oplossings of ontoelaatbaarhede te identi seer, maar dit kan potensieel meer voordelig wees om metodes te gebruik wat sistematies meer ekonomiese en e ektiewe oplossings vind. Heuristieke en metaheuristieke word as goeie alternatiewe oplossingsbenaderings aangebied. In hierdie tesis word verskillende metaheuristiekbenaderings toegepas op drie tipiese mengprobleme van verskillende groottes wat vanuit die petrochemiese industrie spruit. 'n Vierde geval met realistiese (regte wêreld) grootte word ook aangebied. Heuristieke word volgens intuïsie ontwikkel terwyl metaheuristieke aangepas word vanuit die literatuur. Lukrake soektegnieke soos die blinde lukrake soektegniek en die plaaslike lukrake soektegniek lewer redelike resultate. Binne die klas van genetiese algoritmes word die beste resultate gelewer wanneer die algoritme met 'n kombinasie van rangorde ksheidstoekenning en toernooiseleksie van individue geïmplimenteer word. Goeie resultate word ook verkry met behulp van tabusoektogbenaderings ten spyte van die kontinue aard van hierdie probleme. Gesimuleerde tempering lewer ook redelike resultate. 'n Vergelyking van die resultate van die verskillende tegnieke toon dat die tabusoektogtegniek die beste resultate met betrekking tot die kwaliteit van die oplossing sowel as uitvoertyd lewer. Gesimuleerde tempering lewer egter die beste resultate met betrekking tot die kwaliteit van die oplossing sowel as uitvoertyd vir die voorgestelde realistiese grootte probleem.

Study project (MComm)--University of Stellenbosch, 2000. / ENGLISH ABSTRACT: The purpose of this assignment is to develop a method for rate making of construction machines and vehicles. An analysis of the fixed and variable cost of machines and vehicles are made together with the allocation of overhead costs. After anal ising the various cost components a model is developed for the determination of depreciation and finance charges by using the utilization of the relevant plant item. The figures obtained from this model are then used in an asset register. The information needed by the Receiver of Revenue is also included in this register for calculating the depreciation value at the end of the financial year. The maintenance and replacement of plant equipment are also discussed. Before the conclusion the necessity of keeping accurate records and the use of budgets for managing are looked at. / AFRIKAANSE OPSOMMING: Die doel van die werkstuk is om 'n raamwerk daar te stel wat gebruik kan word vir tariefvasstelling van konstruksiemasjiene en - voertuie. In Ontleding van die vaste en veranderlike koste van masjinerie en voertuie word gemaak, asook die hantering van oorhoofse koste in die onderneming. Nil die bespreking van die verskillende kostekomponente waaruit 'n tarief bestaan, word die klem geplaas op die berekening van waardevermindering. 'n Model vir waardeverminderingen finansieringskostebepaling aan die hand van die benutting van toerusting word ontwikkel. Die inligting sodoende verkry word saamgevat in 'n bateregister tesame met die inligting noodsaaklik vir die Ontvanger van Inkomste om waardeverminderingafskrywings te maak aan die einde van elke finansiele jaar. Die onderhoud en vervanging van toerusting word ook bespreek. Ter afsluiting word rekordhouding en die opstel van begrotings bespreek en die nut daarvan vir bestuur uitgewys.

Thesis (MComm)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: Global rail reform is an important topic, especially seen against a backdrop of a worldwide requirement to facilitate modal shift back to rail. This modal shift is required because of growing environmental issues and rising freight cost concerns. Appropriate rail reform is also required to create an environment for South Africa’s freight railway to sustainably achieve modal shift to reverse this trend. This research is based on an idealised design approach that postulates an ideal virtual railway for South Africa, based on Transport Economic and market segmentation principles. It is accepted that major investment will be required to realise this ideal railway, but the exact role, positioning, institutional and organisational structures of the railway system require clarification. The established approach to provide this clarification in a typical business is, first and foremost, to understand the market that needs to be served through appropriate market segmentation. In this regard, the research presents: • an overview of South Africa’s surface freight transport industry, including the specific challenges faced by the industry and the historical evolution of the industry; • a benchmarking exercise of South Africa’s rail system against global rail systems; • a summary of global rail reform case references; • the need for transport economic regulation; • an analysis of current total surface freight flows (road and rail) across the geography of the country’s transport corridors, culminating in a freight flow market segmentation for South Africa informed by rail’s economic fundamentals; • the resultant effect of this analysis on the framing of an idealised network design; and • a rail reform proposal based on the idealised design. The research ‘imagines’ that the country has no existing railway system and analyse the manner in which specific freight (commodities and cargo types) actually flows from origin to destination by all modes of transport within the country’s freight logistics industry. The result of the freight market segmentation exercise informs the crafting of an ideal network. Using this ideal network as a starting point, the most appropriate rail reform option is considered against the background of benchmarking the current system. / AFRIKAANSE OPSOMMING: Die wêreldwye beweging vir ‘n modale verskuiwing terug na spoor is ‘n belangrike faktor wanneer spoorhervorming ter sake kom. Dit word as gevolg van die toenemende klem wat op omgewingskwessies gelê word en stygende vervoerkostes, vereis. Toepaslike spoorhervorming is ook in Suid-Afrika belangrik sodat‘n omgewing waarin Suid – Afrika se vragvervoer volhoubaar modale verskuiwing kan bereik, geskep kan word om sodoende ‘n modale verskuiwing te bewerkstellig. Die navorsing in hierdie tesis word op ‘n geïdealiseerde ontwerp benadering gegrond wat die ideale spoorweg vir Suid – Afrika postuleer. Vervoerekonomiese en marksegmenteringsbeginsels vorm die grondslag van die ontwerp. Beduidende investering sal benodig word om hierdie ideale spoorweg te laat realiseer, maar die presiese rol, posisionering, en institusionele en organisatoriese strukture van die spoorwegsisteem is nog onduidelik. Die gevestigde navorsingsgefundeerde benadering om hierdie vraagstuk te benader is om eerstens markvraag deur middel van marksegmentering, te bepaal. In hierdie opsig bied die navorsing: • ‘n oorsig van Suid–Afrika se landvragvervoerbedryf, insluitend die spesifieke uitdagings en historiese evolusie van die bedryf; • ‘n nomrstellingsoefening van Suid–Afrika se spoorsisteem teen globale spoorsisteme; • ‘n opsomming van globale spoorhervorminggevallestudies; • die behoefte aan vervoerekonomiese regulering; • ‘n analise van die huidige landvragvloeivolumes (pad en spoor) regoor die land se vervoerkorridors wat in ‘n vragvloeimarksegmentering vir Suid–Afrika uitloop, • die gevolglike effek van die analise op die ontwerp van ‘n geïdealiseerde network; en • ‘n spoorhervormingvoorstel gegrond op die geïdealiseerde ontwerp. Hierdie navorsing gebruik ‘n virtuele benadering naamlik dat die land geen bestaande spoorwegsisteem het nie en analiseer die vraag na vervoer op die fynste moontlike vlak. Die resultaat van die vragsegmenteringoefening word gebruik om die ideale netwerk te bou. Deur die gebruik van die ideale netwerk as ‘n uitgangspunt word die mees geskikte spoorhervormingopsie oorweeg met normstelling van die huidige sisteem as ‘n vergelykende agtergrond.