Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/84729
Type: Thesis
Title: Application of memory-based approach to multi-objective optimisation on dynamic resource-constrained project scheduling with time-varying number of tasks.
Author: Abello, Manuel Blanco
Issue Date: 2014
School/Discipline: School of Computer Science
Abstract: Many, if not all, manufacturing processes in industry require scheduling activities; such activities are very important as often they determine the success or failure of some companies. For example, in wine production, grapes are planted, mature fruits are harvested, transported and crushed then the juice obtained is placed in tanks, which are managed during fermentation, and finally the wine is bottle. A schedule can be a solution to a problem which has several, possibly conflicting objectives, e.g. the mininisation of production costs and delays while meeting customer-imposed wine delivery times; the problem also has constraints, e.g. a bottling line cannot be used without being cleaned to process white wine when it last processed red wine. As can be expected, the problem has variables such as the number of wine bottles ordered. The environment (e.g. wine factory) in which the schedule is implemented may change (e.g. one bottling line breaks down) whereby this schedule becomes infeasible. Consequently, there could be a need to solve a new scheduling problem to obtain a new schedule best suited to the new state of the environment. The number of variables in this new problem may be the same as that of the previous problem. A large proportion of research effort has been directed towards scheduling problems with a constant number of variables despite changes in the environments where the problems are set. However, there are important scheduling problems where the number of variables could vary. For example, in some models of job-shop scheduling problems there are occurrences of additional rush jobs and job cancellations. This thesis deals with one particular class of scheduling problems, each being multi-objective, resource constrained, and having numbers and values of variables which vary over time. Various traditional operation research methods as well as a few Artificial Intelligence-based techniques, such as Multi-Agent Systems and Evolutionary Algorithms (EA), have been applied to solve this type of problem. In this thesis, a memory-based EA technique was applied to solve problems from the class. Being memory-based, this technique utilises the solutions to problems set in previous states of an environment in order to solve a problem set in the current state of this environment. The memory-based EA technique, referred to as Centroid-Based Adaptation with Random Immigrants (CBAR), is applicable only to solve multi-objective, resource-constrained problems with a constant number of variables. In this thesis, CBAR is extended to become applicable to solve all problems from the above-mentioned class. The result of this extension is a technique referred to as Mapping of Task IDs for CBAR (McBAR). This thesis investigates the performance, the performance stability over environmental dynamics, and the efficiency of McBAR for solving various problems from the above class, legitimises the sub-algorithms that constitute McBAR and extends McBAR to become proactive (anticipative of future environmental changes). Compared to the other techniques investigated in this thesis, results showed McBAR to have the best and most stable performance, and to be most efficient for determining solutions to problems from the above class. All of the sub-algorithms of McBAR are shown to be legitimate, while McBAR having been made proactive is shown to be beneficial in some applications.
Advisor: Michalewicz, Zbigniew
Bui, Lam Thu
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2014
Keywords: resource-constrained project scheduling; dynamic environments; multi-objective optimisation; response surface methodology; universal intelligence; lagrange optimisation
Provenance: This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at: http://www.adelaide.edu.au/legals
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf260.88 kBAdobe PDFView/Open
02whole.pdf2.73 MBAdobe PDFView/Open
PermissionsLibrary staff access only232.42 kBAdobe PDFView/Open
RestrictedLibrary staff access only5.48 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.