This thesis compares different mixed integer programming (MIP) formulations for sequencing of tasks in the context of avionics scheduling. Sequencing is a key concern in many discrete optimisation problems, and there are numerous ways of accomplishing sequencing with different MIP formulations. A scheduling tool for avionic systems has previously been developed in a collaboration between Saab and Linköping University. This tool includes a MIP formulation of the scheduling problem where one of the model components has the purpose to sequence tasks. In this thesis, this sequencing component is replaced with other MIP formulations in order to study whether the computational performance of the scheduling tool can be improved. Different scheduling instances and objective functions have been used when performing the tests aiming to evaluate the performances, with the computational times of the entire avionic scheduling model determining the success of the different MIP formulations for sequencing. The results show that the choice of MIP formulation makes a considerable impact on the computational performance and that a significant improvement can be achieved by choosing the most suitable one.

This thesis introduces a Large Neighborhood Search (LNS) method to solve a multi-processor avionics scheduling problem. In a typical scheduling problem, tasks are scheduled with exact starting times. In this thesis however, tasks will instead be assigned to disjoint time segments, called buckets. For an assignment to be feasible, precedence relations and capacity constraints related to network and computing resources need to be fulfilled. The introduced LNS method relies on solving Mixed-Integer Programming (MIP)-models. To make progress in the search for a feasible assignment, we construct a MIP-model that allows violation of the problem constraints at a cost of increased objective value. The LNS method uses two operators, a destroy operator that chooses a set of tasks that are allowed to change buckets, and a repair operator that through solving the MIP-model creates a new schedule. This thesis develops 11 types of destroy operators and 30 (concrete) variants of them. The MIP-based LNS is evaluated on a set of 60 instances with up to 84 000 tasks and 21 processors. The instances belongs to six categories of varying difficulty. The MIP-based LNS solves 50 instances within our time limit, and the largest instance solved has 77 757 tasks. This is significantly better than solving the complete MIP-model in a single step. With this approach only 36 instances can be solved within our time limit and the largest instance solved has 48554 tasks.