Sample path optimization techniques for dynamic resource allocation in discrete event systems (Stochastic optimization).

摘要

The main focus of this dissertation is the dynamic allocation of discrete-resources in the context of Discrete Event Systems (DES). For this purpose, we develop two algorithms that can be used to address such problems. The first one, is descent, in other words at every iteration proceeds to an allocation with a lower cost, and it is suitable for problems with separable convex structure. Furthermore, at every iteration it visits feasible allocations which makes it appropriate for use on-line. The second one, is incremental, that is, it starts with zero resources, and at every step it allocates an additional resource. Both algorithms are proven to converge in deterministic as well as stochastic environments. Furthermore, because they are driven by ordinal comparisons they are robust with respect to estimation noise and converge fast.; To complement the implementation of the derived optimization algorithms we develop two techniques for predicting the system performance under several parameters while observing a single sample path under a single parameter. The first technique, Concurrent Estimation, can be directly applied to general DES. On the other hand, for the second one, referred to as Finite Perturbation Analysis (FPA), we demonstrate a general procedure for deriving this algorithm from the system dynamics. Moreover, both procedures can be used for systems with general event lifetime distributions.; The dissertation ends with three applications of variations of the developed resource allocation methodologies on three practical problems. First, the incremental algorithm is used on a kanban-based manufacturing system to find the kanban allocation that optimizes a given objective function (e.g., throughput, mean delay). Next, a variation of the descent algorithm is used to resolve the channel allocation problem in cellular telephone networks as to minimize the number of lost calls. Finally, a combination of the FPA and kanban approaches are used to solve the ground holding problem in air traffic control to minimize the congestion over busy airports.