Optimized Scheduling of Complex Resource Allocation Systems through Approximate Dynamic Programming

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This grant provides funding for the development of a novel framework for managing the complex resource allocation that takes place in contemporary production and service systems. A defining characteristic of this framework is the decomposition of the overall resource allocation problem encountered in the aforementioned environments into two major sub-problems: The first of these sub-problems is known as the Logical or Behavioral Control problem for the target environments, and it seeks to prevent the development of problematic or undesirable patterns in the system behavior. The methodological base for addressing this sub-problem is a body of results provided by Qualitative Discrete Event Systems (DES) theory. The second sub-problem is known as the Performance Control or Scheduling problem, and it seeks to optimize some chosen performance indices within the behavioral latitude provided by the logical controller that is returned by the first sub-problem. The methodological base for this second sub-problem is provided by the theory of Markov Decision Processes (MDP) and some more recent developments in it, collectively known as Approximate Dynamic Programming (ADP). In the proposed investigations, special emphasis is placed on the very high computational complexity that typically underlies the aforementioned problems, and the pursued solutions will seek to provide explicit levers that will enable the system designers to systematically trade-off computational and operational efficiencies. Finally, the proposed theoretical developments will be concretized by applying them to the problems of throughput maximization of (i) flexibly automated production cells and (ii) industrial Automated Guided Vehicle (AGV) systems. If successful, the results of this research will bring closer the existing developments in scheduling theory to the field practice, since they will help to deal more effectively with the underlying complexities. In this way, they will enable and promote the concurrency and the operational flexibilities that have been frequently envisioned for many contemporary applications, but have been limited in practice by the current inability to master the operational complexity that stems from these concepts. At a more analytical level, the proposed research will further promote the burgeoning area of ADP and it will identify and pursue new interesting synergies between this area and Qualitative DES theory. Finally, on the educational side, the proposed program will promote and strengthen the presence of the DES and ADP theories in the graduate engineering curriculum, and it will give the opportunity to a number of graduate students to experience the potential of these theories and their results, through active participation in the pursued research.