Deterministic optimisation considers problems in which a decision-maker makes a single strategic decision, which are commonly formulated as mixed-integer linear programmes (MILPs). In contrast, stochastic dynamic optimisation considers problems involving sequential operational decisions in a random environment, typically modelled as Markov decision processes (MDPs). Separate still is bi-objective optimisation, in which trade-offs between competing objectives are explored. Frameworks that integrate strategic and operational decisions through MILPs and MDPs can be known as MDP Design frameworks, and the existing literature on this is limited to two prior studies each with their own approach, highlighting the complexity of merging these two disparate types of decision making. Furthermore, no previous attempts have been made to introduce multiple objectives into MDP Design. This thesis lies at the intersection of deterministic, stochastic dynamic, and bi-objective optimisation, seeking to answer questions as to how to formalise such problems, how to optimise such problems either exactly or approximately, and how the resulting modelling framework and solution methodologies can be applied in the context of redundancy allocation, i.e. the allocation of copies or backups of components in some system to improve its reliability, and the operational decisions as to how to maintain such systems to balance between reliability and costs. This thesis provides a novel MDP Design framework that is well-suited to modelling more complex structural relationships between design decisions and the resulting state and action spaces of the MDP. Any problem within this framework is a MILP, and can therefore be solved exactly by a MILP solver. However, this is known to be computationally expensive, so approximate solution methodologies are required to solve larger problems. A common theme throughout this thesis is the use of decomposition to break problems up into smaller subproblems, either breaking the strategic and operational stages of the MDP Design problem back into two distinct phases, or breaking a large and specially structured MDP down into smaller MDPs. The computational results show that these methods are effective, with a massive improvement in terms of scalability to larger problem instances, and solution quality comparable to that of the exact solver on smaller instances. The results of these experiments demonstrate that solving problems with the proposed MDP Design framework is not beyond the current capabilities of Operational Research. As such, especially when paired with the structural flexibility of the framework, it is believed that these modelling and solution techniques could be suited to the integration of problems outside of system design and maintenance.
Luke Fairley (Thu,) studied this question.