Computational Strategies for Model Predictive Control on Switching Max-plus Linear Systems

Computational Strategies for Model Predictive Control on Switching Max-plus Linear Systems

Vos, Daniël (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Mechanical, Maritime and Materials Engineering)

van den Boom, Ton (mentor)
van der Woude, Jacob (mentor)
Gupta, Abhimanyu (mentor)
Aardal, Karen (graduation committee)

Delft University of Technology

Applied Mathematics

2019-11-29

A switching max-plus linear model is a framework to describe the discrete dynamics of the timing of events. To influence these systems one can choose the routes of jobs and the orderings of operations as input for the system. In this thesis the techniques of model predictive control are used to find good input values. The problem of finding the optimal input is however NP-hard, which means there is no guarantee to find the optimal in a reasonable amount of time. This is an issue for model predictive control on real applications of the switching max-plus model. In applications, on-line performance is used where there is limited time to compute the input values for control.\\ This thesis takes a look into methods to reduce the computational complexity of the MPC-SMPL problem. Alternative formulations such as reparameterization, model based-partitioning and the cutting plane method are developed and tested for the MPC-SMPL problem. To solve the MPC-SMPL problem 3 heuristics are designed and implemented for simulation. The heuristics are partition-based optimization, tabu search and simulated annealing. The goal is to find a strategy that obtains the best solution to the problem in a limited amount of time.

max-plus algebra
Scheduling
integer programming
Model Predictive Control
discrete event simulation
tabu search
simulated annealing
model based partitioning
Distributed Optimization

http://resolver.tudelft.nl/uuid:9ba7db70-aa7e-499b-8370-9120e2b197d4

Double degree for the Master of Science in Applied Mathematics and Systems and Control.

Student theses

master thesis

© 2019 Daniël Vos