Application of memory-based approach to multi-objective optimisation on dynamic resource-constrained project scheduling with time-varying number of tasks.

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.