Development of a scheduling model and solution algorithms for carriers in the automotive manufacturing environment

Marx, J. D. (2006-04)

Thesis (MscIng) -- University of Stellenbosch, 2006.

Thesis

ENGLISH ABSTRACT: The aim of this thesis was to develop a scheduling model and solution algorithms for a generic problem that can be used to solve a scheduling problem at Autocarriers. The main characteristics of the generic problem are the following: Transporters are required to deliver various containers (each having a specific origin vertex and destination vertex) by transporting them through a network. Each transporter has a restricted cargo capacity which is a function of the number and types of containers loaded on the transporter. Containers can be stored temporarily at any vertex so that they can be moved by one or more transporters. Costs are incurred by delivering containers later than the required time and for transporters moving along the arcs of the network. A problem definition was created that describes the various entities of the generic problem. The problem definition was used to develop a scheduling model consisting of an objective function and a solution space. The solution space is defined by a set of conditions that describes all valid solutions to the problem. Two heuristic algorithms were developed to generate solutions to the problem. The maximum service level algorithm attempts to deliver containers on time without any regard to the cost involved. The second algorithm, the minimum total cost algorithm, attempts to minimise the sum of the costs of the problem. A software tool was developed that can be used to define an instance (or specific occurrence) of the generic problem and solve the problem approximately by means of the solution algorithms. The software tool has a simulation capability that is useful for evaluating the solution algorithms; hence various changes to a problem can be evaluated.

AFRIKAANSE OPSOMMING: Die doel van hierdie projek was om 'n skeduleringsmodel en oplossingsalgoritmes te ontwikkel vir 'n generiese problem. Hierdie model kan gebruik word om 'n skeduleringsprobleem by Autocarriers op te las. Die belangrikste kenmerke van die generiese probleem kan soos volg uiteengesit word: Vervoeroperateurs word benodig om verskeie houers deur 'n netwerk te vervoer. Elke houer het 'n spesifieke oorsprongsnode en bestemmingsnode. Die vervoeroperateurs het 'n beperkte laaikapasiteit wat afhanklik is van die aantal houers van elke tipe wat opgelaai word. Die houers kan tydelik by enige node gestoor word sodat hulle deur een of meer vervoeroperateurs vervoer kan word. Kostes word toegeken vir die laat aflewering van houers sowel as vir die beweging van vervoeroperateurs deur die netwerk. 'n Probleemdefinisie is ontwikkel wat die verskillende entiteite in die probleem omskryf. Die probleemdefinisie is gebruik om 'n skeduleringsmodel te ontwikkel wat bestaan uit 'n doelwitfunksie en 'n oplossingsruimte. Die oplossingsruimte is gedefinieer deur 'n stel voorwaardes wat alle geldige oplossings beskryf. Twee heuristiese algoritmes is ontwikkel om oplossings vir die probleem te genereer. Die maksimum diensvlak algoritme het die betydse aflewering van houers ten doel, sander in agneming van die gepaardgaande koste. Die tweede algoritme, die minimum totale koste algoritme, poog om die som van die verskeie kostes van die probleem te minimeer. 'n Sagtewarepakket is ontwikkel wat gebruik kan word om 'n probleemgeval te definieer wat in ooreenstemming is met die generiese probleem. Die sagtewarepakket kan hierdie probleem met behulp van die oplossingsalgoritmes oplos. 'n Simulasiefunksionaliteit is in die sagtewarepakket aangebring sodat die algoritmes evalueer kan word. Gevolglik kan die invloed van verskeie veranderinge aan die probleemgeval ondersoek word.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/50597
This item appears in the following collections: