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

This paper is concerned with the basic structure of optimal control of discrete-event dynamic processes defined over a max-plus algebra. Only a simple system is being considered, namely a single server processing a given sequence of jobs, but the structural conditions that are discovered may lead to extensions to 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 discrepancy between the completion times and given desired due dates. The concept of the costate is being 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.