Dans les réseaux d'accès sans fil, l'un des défis les plus récents est la réduction de la consommation d'énergie du réseau, tout en préservant la qualité de service perçue par les utilisateurs finaux. Cette thèse propose des solutions à ce problème difficile considérant deux objectifs, l'économie d'énergie et la minimisation du délai de transmission. Comme ces objectifs sont contradictoires, un compromis devient inévitable. Par conséquent, nous formulons un problème d’optimisation multi-objectif dont le but est la minimisation conjointe de la puissance consommée et du délai de transmission dans les réseaux sans-fil. La minimisation de la puissance est réalisée en ajustant le mode de fonctionnement des stations de base (BS) du réseau d’un niveau élevé de puissance d’émission vers un niveau d'émission plus faible ou même en mode veille. La minimisation du délai de transmission est réalisée par le meilleur rattachement des utilisateurs avec les BS du réseau. Nous couvrons deux réseaux sans-fil différents en raison de leur pertinence : les réseaux locaux sans-fil (IEEE 802.11 WLAN) et les réseaux cellulaires dotés de la technologie LTE. / In wireless access networks, one of the most recent challenges is reducing the power consumption of the network, while preserving the quality of service perceived by the end users. The present thesis provides solutions to this challenging problem considering two objectives, namely, saving power and minimizing the transmission delay. Since these objectives are conflicting, a tradeoff becomes inevitable. Therefore, we formulate a multi-objective optimization problem with aims of minimizing the network power consumption and transmission delay. Power saving is achieved by adjusting the operation mode of the network Base Stations (BSs) from high transmit power levels to low transmit levels or even sleep mode. Minimizing the transmission delay is achieved by selecting the best user association with the network BSs. We cover two different wireless networks, namely IEEE 802.11 wireless local area networks and LTE cellular networks.

Les problèmes d’optimisation multi-objectifs mènent souvent à considérer des ensembles de points non-dominés très grands à mesure que la taille et le nombre d’objectifs du problème augmentent. Générer l’ensemble de ces points demande des temps de calculs prohibitifs. De plus, la plupart des solutions correspondantes ne sont pas pertinentes pour un décideur. Une autre approche consiste à utiliser des informations de préférence, ce qui produit un nombre très limité de solutions avec des temps de calcul réduits. Cela nécessite la plupart du temps une élicitation précise de paramètres. Cette étape est souvent difficile pour un décideur et peut amener à délaisser certaines solutions intéressantes. Une approche intermédiaire consiste à raisonner avec des relations de préférences construites à partir d’informations partielles. Nous présentons dans cette thèse plusieurs modèles de relations partielles de préférences. En particulier, nous nous sommes intéressés à la génération de l’ensemble des points non-dominés selon ces relations. Les expérimentations démontrent la pertinence de notre approche en termes de temps de calcul et qualité des points générés. / Multi-objective optimization problems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models.In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Sanjoy Das / Anil Pahwa / The task of short-term optimal thermal generation scheduling can be cast in the form of a multi-objective optimization problem. The goal is to determine an optimal operating strategy to operate power plants, in such a way that certain objective functions related to economic and environmental issues, as well as transmission losses are minimized, under typical system and operating constraints. Due to the problem’s inherent complexity, and the large number of associated constraints, standard multi-objective optimization algorithms fail to yield optimal solutions. In this dissertation, a novel, two-phase multi-objective evolutionary approach is proposed to address the short-term optimal thermal generation scheduling problem. The objective functions, which are based on operation cost, emission and transmission losses, are minimized simultaneously. During the first phase of this approach, hourly optimal dispatches for each period are obtained separately, by minimizing the operation cost, emission and transmission losses simultaneously. The constraints applied to this phase are the power balance, spinning reserve and power generation limits. Three well known multi-objective evolutionary algorithms, NSGA-II, SPEA-2 and AMOSA, are modified, and several new features are added. This hourly schedule phase also includes a repair scheme that is used to meet the constraint requirements of power generation limits for each unit as well as balancing load with generation. The new approach leads to a set of highly optimal solutions with guaranteed feasibility. This phase is applied separately to each hour long period. In the second phase, the minimum up/down time and ramp up/down rate constraints are considered, and another improved version of the three multi-objective evolutionary algorithms, are used again to obtain a set of Pareto-optimal schedules for the integral interval of time (24 hours). During this phase, the hourly optimal schedules that are obtained from the first phase are used as inputs. A bi-objective version of the problem, as well as a three-objective version that includes transmission losses as an objective, are studied. Simulation results on four test systems indicate that even though NSGA-II achieved the best performance for the two-objective model, the improved AMOSA, with new features of crossover, mutation and diversity preservation, outperformed NSGA-II and SPEA-2 for the three-objective model. It is also shown that the proposed approach is effective in addressing the multi-objective generation dispatch problem, obtaining a set of optimal solutions that account for trade-offs between multiple objectives. This feature allows much greater flexibility in decision-making. Since all the solutions are non-dominated, the choice of a final 24-hour schedule depends on the plant operator’s preference and practical operating conditions. The proposed two-phase evolutionary approach also provides a general frame work for some other multi-objective problems relating to power generation as well as in other real world applications.

Linear programming is widely used to solve various complex problems with many variables, subject to multiple constraints. Expert systems are created to provide expertise on complex problems through the application of inference procedures and advanced expert knowledge on facts relevant to the problem. The diet problem is well-known for its contribution to the development of linear programming. Over the years many variations and facets of the diet problem have been solved by means of linear programming techniques and expert systems respectively. In this study the feasibility of combining expert system technology and linear programming techniques to solve a diet problem topical to South Africa, is examined. A computer application is created that incorporates goal programming- and multi-objective linear programming models as the inference engine of an expert system. The program is successfully applied to test cases obtained through knowledge acquisition. The system delivers an eating-plan for an individual that conforms to the nutritional requirements of a healthy diet, includes the personal food preferences of that individual, and includes the food items that result in the lowest total cost. It further allows prioritization of the food preference and least cost factors through the use of weights. Based on the results, recommendations and contributions to the linear programming and expert system fields are presented. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2014

Linear programming is widely used to solve various complex problems with many variables, subject to multiple constraints. Expert systems are created to provide expertise on complex problems through the application of inference procedures and advanced expert knowledge on facts relevant to the problem. The diet problem is well-known for its contribution to the development of linear programming. Over the years many variations and facets of the diet problem have been solved by means of linear programming techniques and expert systems respectively. In this study the feasibility of combining expert system technology and linear programming techniques to solve a diet problem topical to South Africa, is examined. A computer application is created that incorporates goal programming- and multi-objective linear programming models as the inference engine of an expert system. The program is successfully applied to test cases obtained through knowledge acquisition. The system delivers an eating-plan for an individual that conforms to the nutritional requirements of a healthy diet, includes the personal food preferences of that individual, and includes the food items that result in the lowest total cost. It further allows prioritization of the food preference and least cost factors through the use of weights. Based on the results, recommendations and contributions to the linear programming and expert system fields are presented. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2014

Hyper-heuristics is a new field of optimisation which has recently emerged and is receiving growing exposure in the research community and literature. Hyper-heuristics are optimisation methods which are designed with a high level of abstraction from any one specific problem or class of problems and therefore are more generally applicable than specialised meta-heuristic and heuristic methods. Instead of being designed to solve a specific real-world problem, hyper-heuristics are designed to solve the problem of heuristic generation and selection. As such, hyper-heuristics can be thought of as methods for optimising the operations of an optimisation process which finds good solutions to a problem as a by-product. This approach has been shown to be very effective and in some cases provides improvement in search performance as well as reducing the burden associated with tailoring meta-heuristics which is often required when solving new problems. In this thesis, the hypothesis that hyper-heuristics can be competitively applied to real-world multi-objective optimisation problems such as the water distribution design problem is tested. Although many single-objective hyper-heuristics have been proposed in the literature, only a few multi-objective methods have been proposed. This thesis explores two different novel multi-objective hyper-heuristics: one designed for generating new specialised heuristics; and one designed for solving the online selection of heuristics. Firstly, the behaviour of a set of heuristics is explored to create a base understanding of different heuristic behavioural traits in order to better understand the hyper-heuristic behaviours and dynamics later in the study. Both approaches are tested on a range of benchmark optimisation problems and finally applied to real-world instances of the water distribution network design problem where the selective hyper-heuristics is demonstrated as being very effective at solving this difficult problem. Furthermore, the thesis demonstrates how heuristic selection can be improved by incorporating a greater level of information about heuristic performance, namely the historical joint performance of different heuristics, and shows that exploiting this sequencing information in heuristic selection can produce highly competitive results.

A majority of the established automotive manufacturers are under severe competitive pressure and their long term economic sustainability is threatened. In particular the transformation towards more CO2-efficient energy sources is a huge financial burden for an already investment capital intensive industry. In addition existing operations urgently need rapid improvement and even more critical is the development of highly productive, efficient and sustainable manufacturing solutions for new and updated products. Simultaneously, a number of severe drawbacks with current improvement methods for industrial production systems have been identified. In summary, variation is not considered sufficient with current analysis methods, tools used are insufficient for revealing enough knowledge to support decisions, procedures for finding optimal solutions are not considered, and information about bottlenecks is often required, but no accurate methods for the identification of bottlenecks are used in practice, because they do not normally generate any improvement actions. Current methods follow a trial-and-error pattern instead of a proactive approach. Decisions are often made directly on the basis of raw static historical data without an awareness of optimal alternatives and their effects. These issues could most likely lead to inadequate production solutions, low effectiveness, and high costs, resulting in poor competitiveness. In order to address the shortcomings of existing methods, a methodology and framework for manufacturing management decision support using simulation-based multi-objective optimisation is proposed. The framework incorporates modelling and the optimisation of production systems, costs, and sustainability. Decision support is created through the extraction of knowledge from optimised data. A novel method and algorithm for the detection of constraints and bottlenecks is proposed as part of the framework. This enables optimal improvement activities with ranking in order of importance can be sought. The new method can achieve a higher improvement rate, when applied to industrial improvement situations, compared to the well-established shifting bottleneck technique. A number of 'laboratory' experiments and real-world industrial applications have been conducted in order to explore, develop, and verify the proposed framework. The identified gaps can be addressed with the proposed methodology. By using simulation-based methods, stochastic behaviour and variability is taken into account and knowledge for the creation of decision support is gathered through post-optimality analysis. Several conflicting objectives can be considered simultaneously through the application of multi-objective optimisation, while objectives related to running cost, investments and other sustainability parameters can be included through the use of the new cost and sustainability models introduced. Experiments and tests have been undertaken and have shown that the proposed framework can assist the creation of manufacturing management decision support and that such a methodology can contribute significantly to regaining profitability when applied within the automotive industry. It can be concluded that a proof-of-concept has been rigorously established for the application of the proposed framework on real-world industrial decision-making, in a manufacturing management context.

This dissertation addresses resource allocation problems that occur in both public and private health care settings with the objective of characterizing the tradeoffs that occur when simultaneously incorporating multiple objectives and developing methods to address these tradeoffs. We examine three resource allocation problems (i) strategic allocation of financial resources and limited staffing capacity for the mobile delivery of health care within African countries, (ii) real-time allocation of hospital beds to internal patient requests, and (iii) development of patient redirection policies in response to limited bed availability in units within a system of hospitals. For each problem we define models, each with a different methodology, and utilize the models to develop allocation strategies that account for multiple competing objectives and examine the performance of the strategies with computational studies. In Chapter 2, we model African health care delivery systems utilizing a mixed-integer program (MIP) which accounts for financial and personnel constraints as well as infrastructure quality. We characterize tradeoffs in effectiveness, efficiency, and equity resulting from four allocation strategies with computational experiments representing the variety of spatial patterns that occur throughout the continent. The main contributions include (i) the development of a model that incorporates spatial and infrastructure characteristics and allows for a study of equity in the delivery of care, rather than access to care, and (ii) the characterization of tradeoffs in the three objectives under a variety of settings. In Chapter 3, we model the real-time assignment of bed requests to available beds as a queueing system and a Markov decision process (MDP). Through the development of bed assignment algorithms and simulation experiments, we illustrate the value of implementing strategic bed assignment practices which balance the bed management objectives of timeliness and appropriateness of assignments. The main contributions of this section include (i) the development of new bed assignment algorithms which use stochastic optimization techniques and outperform algorithms which mimic processes currently used in practice and (ii) the definition of a model and methods for the control of a large complex system that includes flexible units, multiple patient types, and type-dependent routing. In Chapter 4, we model the impact of a patient redirection policy in a hospital unit as a Markov chain. Assuming preferences for patient redirection are aligned with costs, we examine the impact of incremental changes to redirection policies on the probability of the unit being completely occupied, the long-run average utilization, and the long-run average cost of redirection. The main contributions of this chapter include (i) the introduction of a model of patient redirection with multiple patient thresholds and patient preference constraints and (ii) the definition of necessary conditions for an optimal patient redirection policy that minimizes the average cost of redirection.

Since the introduction of sustainable development, industries have witnessed significant sustainability challenges. Literature shows that the food industry is concerned about its need for efficient and effective management practices in dealing with perishability and the requirements for conditioned storage and transport of food products that effect the environment. Hence, the environmental part of sustainability demonstrates its significance in this industrial sector. Despite this, there has been little research into environmentally sustainable inventory management of deteriorating items. This thesis presents mathematical modelling based research for production inventory systems in perishable food supply chains. In this study, multi-objective mixed-integer linear programming models are developed to determine economically and environmentally optimal production and inventory decisions for a two-echelon supply chain. The supply chain consists of single sourcing suppliers for raw materials and a producer who operates under a make-to-stock or make-to-order strategy. The demand facing the producer is non-stationary stochastic in nature and has requirements in terms of service level and the remaining shelf life of the marketed products. Using data from the literature, numerical examples are given in order to test and analyse these models. The computational experiments show that operational adjustments in cases where emission and cost parameters were not strongly correlated with supply chain collaboration (where suppliers and a producer operate under centralised control), emissions are effectively reduced without a significant increase in cost. The findings show that assigning a high disposal cost, limit or high weight of importance to perished goods leads to appropriate reduction of expected waste in the supply chain with no major cost increase. The research has made contributions to the literature on sustainable production and inventory management; providing formal models that can be used as an aid to understanding and as a tool for planning and improving sustainable production and inventory control in supply chains involving deteriorating items, in particular with perishable food supply chains.

Thesis (PhD)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: A difficult subclass of engineering optimisation problems is the class of optimisation problems which are dynamic and stochastic. These problems are often of a non-closed form and thus studied by means of computer simulation. Simulation production runs of these problems can be time-consuming due to the computational burden implied by statistical inference principles. In multi-objective optimisation of engineering problems, large decision spaces and large objective spaces prevail, since two or more objectives are simultaneously optimised and many problems are also of a combinatorial nature. The computational burden associated with solving such problems is even larger than for most single-objective optimisation problems, and hence an e cient algorithm that searches the vast decision space is required. Many such algorithms are currently available, with researchers constantly improving these or developing more e cient algorithms. In this context, the term \e cient" means to provide near-optimised results with minimal evaluations of objective function values. Thus far research has often focused on solving speci c benchmark problems, or on adapting algorithms to solve speci c engineering problems. In this research, a multi-objective optimisation algorithm, based on the cross-entropy method for single-objective optimisation, is developed and assessed. The aim with this algorithm is to reduce the number of objective function evaluations, particularly when time-dependent (dynamic), stochastic processes, as found in Industrial Engineering, are studied. A brief overview of scholarly work in the eld of multiobjective optimisation is presented, followed by a theoretical discussion of the cross-entropy method. The new algorithm is developed, based on this information, and assessed considering continuous, deterministic problems, as well as discrete, stochastic problems. The latter include a classical single-commodity inventory problem, the well-known buffer allocation problem, and a newly designed, laboratory-sized recon gurable manufacturing system. Near multi-objective optimisation of two practical problems were also performed using the proposed algorithm. In the rst case, some design parameters of a polymer extrusion unit are estimated using the algorithm. The management of carbon monoxide gas utilisation at an ilmenite smelter is complex with many decision variables, and the application of the algorithm in that environment is presented as a second case. Quality indicator values are estimated for thirty-four test problem instances of multi-objective optimisation problems in order to quantify the quality performance of the algorithm, and it is also compared to a commercial algorithm. The algorithm is intended to interface with dynamic, stochastic simulation models of real-world problems. It is typically implemented in a programming language while the simulation model is developed in a dedicated, commercial software package. The proposed algorithm is simple to implement and proved to be efficient on test problems. / AFRIKAANSE OPSOMMING: 'n Moeilike deelklas van optimeringsprobleme in die ingenieurswese is optimeringsprobleme van 'n dinamiese en stogastiese aard. Sulke probleme is dikwels nie-geslote en word gevolglik met behulp van rekenaarsimulasie bestudeer. Die beginsels van statistiese steekproefneming veroorsaak dat produksielopies van hierdie probleme tydrowend is weens die rekenlas wat genoodsaak word. Groot besluitnemingruimtes en doelwitruimtes bestaan in meerdoelige optimering van ingenieursprobleme, waar twee of meer doelwitte gelyktydig geoptimeer word, terwyl baie probleme ook 'n kombinatoriese aard het. Die rekenlas wat met die oplos van sulke probleme gepaard gaan, is selfs groter as vir die meeste enkeldoelwit optimeringsprobleme, en 'n doeltre ende algoritme wat die meesal uitgebreide besluitnemingsruimte verken, is gevolglik nodig. Daar bestaan tans verskeie sulke algoritmes, terwyl navorsers steeds poog om hierdie algoritmes te verbeter of meer doeltre ende algoritmes te ontwikkel. In hierdie konteks beteken \doeltre end" dat naby-optimale oplossings verskaf word deur die minimum evaluering van doelwitfunksiewaardes. Navorsing fokus dikwels op oplossing van standaard toetsprobleme, of aanpassing van algoritmes om 'n spesi eke ingenieursprobleem op te los. In hierdie navorsing word 'n meerdoelige optimeringsalgoritme gebaseer op die kruis-entropie-metode vir enkeldoelwit optimering ontwikkel en geassesseer. Die mikpunt met hierdie algoritme is om die aantal evaluerings van doelwitfunksiewaardes te verminder, spesi ek wanneer tydafhanklike (dinamiese), stogastiese prosesse soos wat dikwels in die Bedryfsingenieurswese te egekom word, bestudeer word. 'n Bondige oorsig van navorsing in die veld van meerdoelige optimering word gegee, gevolg deur 'n teoretiese bespreking van die kruis-entropiemetode. Die nuwe algoritme se ontwikkeling is hierop gebaseer, en dit word geassesseer deur kontinue, deterministiese probleme sowel as diskrete, stogastiese probleme benaderd daarmee op te los. Laasgenoemde sluit in 'n klassieke enkelitem voorraadprobleem, die bekende buffer-toedelingsprobleem, en 'n nuut-ontwerpte, laboratorium-skaal herkon gureerbare vervaardigingstelsel. Meerdoelige optimering van twee praktiese probleme is met die algoritme uitgevoer. In die eerste geval word sekere ontwerpparameters van 'n polimeer-uittrekeenheid met behulp van die algoritme beraam. Die bestuur van koolstofmonoksiedbenutting in 'n ilmeniet-smelter is kompleks met verskeie besluitnemingveranderlikes, en die toepassing van die algoritme in daardie omgewing word as 'n tweede geval aangebied. Verskeie gehalte-aanwyserwaardes word beraam vir vier-en-dertig toetsgevalle van meerdoelige optimeringsprobleme om die gehalte-prestasie van die algoritme te kwanti seer, en dit word ook vergelyk met 'n kommersi ele algoritme. Die algoritme is veronderstel om te skakel met dinamiese, stogastiese simulasiemodelle van regtew^ereldprobleme. Die algoritme sal tipies in 'n programmeertaal ge mplementeer word terwyl die simulasiemodel in doelmatige, kommersi ele programmatuur ontwikkel sal word. Die voorgestelde algoritme is maklik om te implementeer en dit het doeltre end gewerk op toetsprobleme.