Development of a scheduling model and solution algorithms for carriers in the automotive manufacturing environment
Date
2006-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (MscIng) -- University of Stellenbosch, 2006.
Keywords
Transportation, Automobile industry and trade, Physical distribution of goods -- Management, Dissertations -- Industrial engineering