Dantzig-Wolfe Decomposition Methods and a Greedy LNS Heuristic for Avionics Scheduling

Sammanfattning

Modern aircraft are controlled by software running on a system of interconnected computers, called the avionics system. To make sure that the system works as expected, each software process, called a job, must get enough time and computing resources. One way to achieve this is by scheduling, each job needs to be scheduled both spatially and temporally, i.e. we need to decide on which computer and at what time each job should be executed. The problem of scheduling these jobs is referred to as an avionics scheduling problem. In this thesis, we model an avionics scheduling problem as a parallel machine scheduling problem, with precedence constraints, time windows, and assignment constraints. A time-indexed Mixed Integer Programming (MIP) model is proposed and then decomposed using Dantzig-Wolfe (DW) decomposition, and a column generation method is utilized to solve the Linear Programming(LP)-relaxation of the problem. To generate the initial columns, we introduce a phase one step where a different column generation approach is used to generate the initial columns. Moreover, in our method, we utilize sparse columns to reduce the memory requirement. Next, we also extend this method in two different ways. The first extension is to decompose the time horizon into smaller subhorizons, yielding a faster method at the expense of a weaker optimistic bound. Secondly, we propose a decomposition in which some constraints from the master problem are moved to the subproblems; this method, however, suffers from being significantly slower in terms of computation time. We find that the time-decomposed method is significantly faster than the straightforward LP-relaxed MIP formulation. Finally, we introduce a Large Neighborhood Search(LNS)-based greedy heuristic which lets us construct a feasible schedule froman LP-relaxed solution. Compared to the MIP method, our heuristic is able to find feasible solutions faster and for more of the instances. Additionally, in the cases where we find feasible integer solutions, we also show that they are of good quality, i.e. the relative gap to the LP-relaxed optimum is small.