Predicting Processing Time of Stochastic Switching Max-Plus Systems

Abstract

The goal in this thesis is to make a prediction on the total processing time for logistical systems to complete their tasks. For simple systems that can be described using a regular max plus state space model this is done by calculating the systems eigenvalue and multiplying that by the number of iterations required. But, for more complex systems that can only be described using a switching max-plus state space model such as a production line that can change during production, or a rail network where some rail segments become unavailable at times. If these changes to the system are fully within control of the operator they are easily accounted for when predicting the total processing time. But, if the system switches stochastically then one would need to simulate all possible permutations of operation to know the average processing time of the system. Alternatively, one might approximate this average processing time using some simplified model. We found three main methods to predict the total processing time. Firstly, we can fit a generalized extreme value distribution to a histogram of the systems performance and then extrapolate this distribution function. Secondly, we can fit a marginal cost model to a limited simulation of the system and then extrapolate based on that model. Lastly, we can rewrite the expectation of how long the system might take to go through N iterations to an inequality by adding an arbitrary diagonal matrix S, which if minimized can be used to approximate total processing time. All three prediction methods can, when fitted properly predict at least within 15% accuracy with the fitted extreme value distribution generally performing best. We also found that it is possible to save total processing time using a controller based on the marginal cost model if it is possible to exert some limited control over the mode switching process.