Back

G-92-01

Optimal Control of a Class of DEDS Flow-Shops with State Dependent Processing Times

and

BibTeX reference

We consider a permutation flow-shop with n jobs and m machines, where the jobs 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 to 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 non-convex 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.

, 33 pages

This cahier was revised in January 1993