Title: Scheduling Techniques for Complex Resource Allocation Systems

 

Advisors: 

Dr. Spyros Reveliotis

 

Committee Members:

Dr. Hayriye Ayhan

Dr. Nagi Gebraeel

Dr. Kamran Paynabar

Dr. Douglas Down (McMaster University)

 

Date and Time: Thursday, August 15th, 9:30 am

Location: Groseclose 402

 

Abstract:

 

This research program provides a complete framework for the real-time management of complex sequential resource allocation systems (RAS) with blocking and deadlocking effects in their dynamics. This framework addresses both control objectives of logical correctness and performance optimization for the conisidered RAS.   A more detailed account of the thesis contributions is as follows:   For the logical-correctness part of the presented framework, we leverage some formal Discrete Event System (DES)-based representations of the RAS behavior and we introduce a new class of deadlock avoidance policies (DAPs) for the considered sequential RAS that is characterized as the class of ``maximal linear'' DAPs. We also provide a complete algorithm for enumerating all the elements of this policy class for a broad class of RAS instances. Finally, we present some numerical experimentation that demonstrates the efficacy of the presented algorithm.   For the performance-optimization part of the presented framework, we provide a scheduling methodology that aims to maximize the throughput of complex RAS with blocking and deadlocking effects. This methodology is based on the solution of a pertinent “fluid” relaxation of the addressed scheduling problem, and it is enabled by the pre-established ability to control the underlying RAS for deadlock freedom, and by the further ability to express the corresponding DAP as a set of linear inequalities on the system state.   Furthermore, we strengthen and further formalize these developments by taking advantage of the  representational and analytical capabilities of the Petri net (PN) modeling framework, which is one of the main formal representational frameworks employed by the current DES theory. These capabilities enable a seamless treatment of the behavioral and the time-based dynamics of the underlying RAS, and they also support a notion of ``fluidization'' of these dynamics through the more recent developments in the area of timed and untimed continuous PN models; this last capability was especially critical for the systematic derivation of the sought ``fluid relaxation'' models and formulations. The information that is contained in the developed ``fluid'' models, when combined with the ``linear'' deadlock avoidance policies that have been employed in this work, provide a complete and very efficient controller for the considered RAS.   Finally, we present a ``correction'' algorithm that aims to detect potential suboptimal decisions that might be effected the aforementioned controller and correct them. These ``corrections'' can be effected either in an ``off-line'' mode, by simulating the dynamics of the underlying RAS, or in an ``on-line'' mode where the underlying RAS is fully operational and the necessary corrections are inferred from the observed behavior of the system. In both of these modes, and especially the second one, the ``correction'' algorithm endows the developed control framework with a ``learning'' capability.  From a more methodological standpoint, the results that enableTitle: Scheduling Techniques for Complex Resource Allocation Systems

 

Advisors: 

Dr. Spyros Reveliotis

 

Committee Members:

Dr. Hayriye Ayhan

Dr. Nagi Gebraeel

Dr. Kamran Paynabar

Dr. Douglas Down (McMaster University)

 

Date and Time: Thursday, August 15th, 9:30 am

Location: Groseclose 402

 

Abstract:

 

This research program provides a complete framework for the real-time management of complex sequential resource allocation systems (RAS) with blocking and deadlocking effects in their dynamics. This framework addresses both control objectives of logical correctness and performance optimization for the conisidered RAS.   A more detailed account of the thesis contributions is as follows:   For the logical-correctness part of the presented framework, we leverage some formal Discrete Event System (DES)-based representations of the RAS behavior and we introduce a new class of deadlock avoidance policies (DAPs) for the considered sequential RAS that is characterized as the class of ``maximal linear'' DAPs. We also provide a complete algorithm for enumerating all the elements of this policy class for a broad class of RAS instances. Finally, we present some numerical experimentation that demonstrates the efficacy of the presented algorithm.   For the performance-optimization part of the presented framework, we provide a scheduling methodology that aims to maximize the throughput of complex RAS with blocking and deadlocking effects. This methodology is based on the solution of a pertinent “fluid” relaxation of the addressed scheduling problem, and it is enabled by the pre-established ability to control the underlying RAS for deadlock freedom, and by the further ability to express the corresponding DAP as a set of linear inequalities on the system state.   Furthermore, we strengthen and further formalize these developments by taking advantage of the  representational and analytical capabilities of the Petri net (PN) modeling framework, which is one of the main formal representational frameworks employed by the current DES theory. These capabilities enable a seamless treatment of the behavioral and the time-based dynamics of the underlying RAS, and they also support a notion of ``fluidization'' of these dynamics through the more recent developments in the area of timed and untimed continuous PN models; this last capability was especially critical for the systematic derivation of the sought ``fluid relaxation'' models and formulations. The information that is contained in the developed ``fluid'' models, when combined with the ``linear'' deadlock avoidance policies that have been employed in this work, provide a complete and very efficient controller for the considered RAS.   Finally, we present a ``correction'' algorithm that aims to detect potential suboptimal decisions that might be effected the aforementioned controller and correct them. These ``corrections'' can be effected either in an ``off-line'' mode, by simulating the dynamics of the underlying RAS, or in an ``on-line'' mode where the underlying RAS is fully operational and the necessary corrections are inferred from the observed behavior of the system. In both of these modes, and especially the second one, the ``correction'' algorithm endows the developed control framework with a ``learning'' capability.  From a more methodological standpoint, the results that enable this correcting mechanism are based on the sensitivity analysis of Markov reward processes and the statistical theory of ``ranking \& selection''.   A series of numerical results demonstrate and assess the efficacy of the developed methodology. this correcting mechanism are based on the sensitivity analysis of Markov reward processes and the statistical theory of ``ranking \& selection''. A series of numerical results demonstrate and assess the efficacy of the developed methodology.