Compilation of maintenance schedules based on their key performance indicators for fast iterative interaction

Abstract

Finding the optimal solution for a scheduling problem is hard, both from a computational perspective and because it is frequently difficult to articulate what the user wants. Often there are a range of possible key performance indicators (such as makespan, resource utilisation, and priority of tasks), and thus here can be many objectives that we want to optimise. However, it will typically be hard for the user to state numerical trade-offs between these objectives. Instead, it can be helpful if the user can explore the solution space themselves, to find which compromises between objectives they prefer. This paper demonstrates the use of Multi-valued Decision Diagrams in consideration of scheduling a real maintenance problem, namely the scheduling of Irish Navy dockyard maintenance. We show how candidate schedules can be compiled into MDDs, based on their associated Key Performance Indicators (KPIs). This representation allows the possible values of KPIs to be restricted by the user, and achievable values of other KPIs can be quickly determined, thus enabling fast iterative interaction with the user in order to achieve a satisfactory balance between the KPIs. We experimentally compare the performance of the MDD with that of a database, showing that the MDD can be considerably faster.