Optimal release times in a single server: an optimal control perspective

This paper is concerned with the basic optimal control structure of discrete-event dynamic processes defined over a max-plus algebra. Only a simple system is considered, namely a single server processing a given sequence of jobs, but the structural conditions that are discovered may lead to extensions for more general systems. The problem in question is how to optimally control the completion (output) times of the jobs by assigning their release (input) times, so as to minimize a measure of the difference between the completion times and given desired due dates. The concept of the costate is applied to the discrete dynamics to identify structural optimality conditions, and, in the case of quadratic cost measures, the optimal control is shown to be computable by a state-feedback law that is linear in the max-plus algebra