Optimal control of a class of DEDS: Flow-shops with state-dependent processing times Academic Article uri icon


  • 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.

published proceedings

  • Discrete Event Dynamic Systems

author list (cited authors)

  • Wagneur, E., & Sriskandarajah, C.

citation count

  • 10

complete list of authors

  • Wagneur, E||Sriskandarajah, C

publication date

  • September 1993