Optimal control of a class of DEDS: Flow-shops with state-dependent processing times
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
We consider a permutation flow-shop with n jobs and m machines, where the job processing times are given by a monotone nondecreasing function of the time elapsed since the release of the jobs. In this class of discrete event dynamic systems (DEDS), the dynamics is both event dependent, and time dependent. Unless processing times are constant, it cannot be linearized using the (max, +) algebra. In order to schedule the jobs, we first need to know how to compute the (optimal) value of each schedule, i.e., when the jobs should be released. This optimal control problem is solved here by proving a predictive feedback control law, which holds for any regular performance criterion. Then we derive a Bellman principle for this type of DEDS, and prove closed form control formulas for the minimum of: the makespan (Cmax), the maximum lateness (Lmax), and the maximum tardiness (Tmax). We also prove some minimax theorems for a class of nonconvex maps derived from the dynamics of the system. The optimal control problem is solved in polynomial time, provided the inverse of the processing time functions can be computed in polynomial time. 1993 Kluwer Academic Publishers.
