In this thesis we consider efficient algorithms for matching problems involving preferences, i.e., problems where agents may be required to list other agents that they find acceptable in order of preference. In particular we mainly study the Stable Marriage problem (SM), the Hospitals / Residents problem (HR) and the Student / Project Allocation problem (SPA), and some of their variants. In some of these problems the aim is to find a stable matching which is one that admits no blocking pair. A blocking pair with respect to a matching is a pair of agents that prefer to be matched to each other than their assigned partners in the matching if any. We present an Integer Programming (IP) model for the Hospitals / Residents problem with Ties (HRT) and use it to find a maximum cardinality stable matching. We also present results from an empirical evaluation of our model which show it to be scalable with respect to real-world HRT instance sizes. Motivated by the observation that not all blocking pairs that exist in theory will lead to a matching being undermined in practice, we investigate a relaxed stability criterion called social stability where only pairs of agents with a social relationship have the ability to undermine a matching. This stability concept is studied in instances of the Stable Marriage problem with Incomplete lists (smi) and in instances of hr. We show that, in the smi and hr contexts, socially stable matchings can be of varying sizes and the problem of finding a maximum socially stable matching (max smiss and max hrss respectively) is NP-hard though approximable within 3/2. Furthermore we give polynomial time algorithms for three special cases of the problem arising from restrictions on the social network graph and the lengths of agents’ preference lists. We also consider other optimality criteria with respect to social stability and establish inapproximability bounds for the problems of finding an egalitarian, minimum regret and sex equal socially stable matching in the sm context. We extend our study of social stability by considering other variants and restrictions of max smiss and max hrss. We present NP-hardness results for max smiss even under certain restrictions on the degree and structure of the social network graph as well as the presence of master lists. Other NP-hardness results presented relate to the problem of determining whether a given man-woman pair belongs to a socially stable matching and the problem of determining whether a given man (or woman) is part of at least one socially stable matching. We also consider the Stable Roommates problem with Incomplete lists under Social Stability (a non-bipartite generalisation of smi under social stability). We observe that the problem of finding a maximum socially stable matching in this context is also NP-hard. We present efficient algorithms for three special cases of the problem arising from restrictions on the social network graph and the lengths of agents’ preference lists. These are the cases where (i) there exists a constant number of acquainted pairs (ii) or a constant number of unacquainted pairs or (iii) each preference list is of length at most 2. We also present algorithmic results for finding matchings in the spa context that are optimal with respect to profile, which is the vector whose ith component is the number of students assigned to their ith-choice project. We present an efficient algorithm for finding a greedy maximum matching in the spa context — this is a maximum matching whose profile is lexicographically maximum. We then show how to adapt this algorithm to find a generous maximum matching — this is a matching whose reverse profile is lexicographically minimum. We demonstrate how this approach can allow additional constraints, such as lecturer lower quotas, to be handled flexibly. We also present results of empirical evaluations carried out on both real world and randomly generated datasets. These results demonstrate the scalability of our algorithms as well as some interesting properties of these profile-based optimality criteria. Practical applications of spa motivate the investigation of certain special cases of the problem. For instance, it is often desired that the workload on lecturers is evenly distributed (i.e. load balanced). We enforce this by either adding lower quota constraints on the lecturers (which leads to the potential for infeasible problem instances) or adding a load balancing optimisation criterion. We present efficient algorithms in both cases. Another consideration is the fact that certain projects may require a minimum number of students to become viable. This can be handled by enforcing lower quota constraints on the projects (which also leads to the possibility of infeasible problem instances). A technique of handling this infeasibility is the idea of closing projects that do not meet their lower quotas (i.e. leaving such project completely unassigned). We show that the problem of finding a maximum matching subject to project lower quotas where projects can be closed is NP-hard even under severe restrictions on preference lists lengths and project upper and lower quotas. To offset this hardness, we present polynomial time heuristics that find large feasible matchings in practice. We also present ip models for the spa variants discussed and show results obtained from an empirical evaluation carried out on both real and randomly generated datasets. These results show that our algorithms and heuristics are scalable and provide good matchings with respect to profile-based optimality.

Machine failure is often an important source of variability and so it is essential to model breakdowns in manufacturing simulation models accurately. This thesis describes the modelling of machine breakdown durations in simulation models of engine assembly lines. To simplify the inputs to the simulation models for complex machining and assembly lines, the Arrows classification method has been derived to group machines with similar distributions of breakdown durations, where the Two-Sample Cram´er-von Mises statistic and bootstrap resampling are used to measure the similarity of two sets of data. We use finite mixture distributions fitted to the breakdown durations data of groups of machines as the input models for the simulation models. We evaluate the complete modelling methodology that involves the use of the Arrows classification method and finite mixture distributions, by analysing the outputs of the simulation models using different input distributions for describing the machine breakdown durations. Details of the methods and results of the grouping processes will be presented, and will be demonstrated using examples.

No description available.

This research work developed an innovative computational approach to the preliminary design of low-thrust trajectories optimising multiple mission criteria. Low-Thrust (LT) propulsion has become the propulsion system of choice for a number of near Earth and interplanetary missions. Consequently, in the last two decades a good wealth of research has been devoted to the development of computational method to design low-thrust trajectories. Most of the techniques, however, minimise or maximise a single figure of merit under a set of design constraints. Less effort has been devoted to the development of efficient methods for the minimisation (or maximisation) of two or more figures of merit. On the other hand, in the preliminary mission design phase, the decision maker is interested in analysing as many design solutions as possible against different trade-off criteria. Therefore, in this PhD work, an innovative Multi-Objective (MO), memetic optimisation algorithm, called Multi-Agent Collaborative Search (MACS2), has been implemented to tackle low-thrust trajectory design problems with multiple figures of merit. Tests on both academic and real-world problems showed that the proposed MACS2 paradigm performs better than or as well as other state-of-the-art Multi-Objective optimisation algorithms. Concurrently, a set of novel approximated, first-order, analytical formulae has been developed, to obtain a fast but reliable estimation of the main trade-off criteria. These formulae allow for a fast propagation of the orbital motion under a constant perturbing acceleration. These formulae have been shown to allow for the fast and relatively accurate propagation of long LT trajectories under the typical acceleration level delivered by current engine technology. Various applications are presented to demonstrate the validity of the combination of the analytical formulae with MACS2. Among them, the preliminary design of the JAXA low-cost DESTINY mission to L2, a novel approach to the optimisation under uncertainty of deflection actions for Near Earth Objects (NEO), and the de-orbiting of space debris with low-thrust and with a combination of low-thrust and solar radiation pressure.