Study On Algorithms For Optimizing Several Classes Of Discrete Event Dynamic Systems

Abstract This master thesis focuses on three practical problems in discrete event dynamicsystem (DEDS), and develops ef?cient algorithms for these problems by analyzing thedif?culties from the viewpoint of the two elements in optimization, i.e., evaluation andsearch. Firstly, we face a problem from manufacturing systems modeled by fork-joinqueueing networks, in which all decisions are evaluated by expected values. To handlethis dif?culty in the evaluation element, we extend ordinal optimization method fromsingle objective to multi-objective, and develop a framework of DEDS multi-objectivealgorithms. Then, we analyze the problem of prematurity in search element, roughlyexplain the prematurity problem in the sense of multi-objective, and develop a newmulti-objective algorithm, called PSEA, which has much better ability of avoiding pre-maturity than the two state-of-art algorithms, NSGA-II and SPEA2 at the price of theconvergence speed. Secondly, we study an asynchronous circuit design problem formulated by cyclictiming constraint graph with min-max constraints, in which all decisions are evaluatedby extreme values. After analyzing its dif?culties and comparing with the previous one,we ?nd that the framework in the previous one can also applied in this problem. Thenwe focus on solving the problem of time separation of events. We establish a suf?cientand necessary structure condition for this problem, and extend CyclicApproxSep, thestate-of-art algorithm, to a larger application area and improve its computed boundsbased on the structure condition. Thirdly, we work on the dynamic voltage scaling problem from sensor networks,which is non-preempt and has aperiodic tasks. Its main dif?culty is concentrated on thesearch element. To meet the strict limitation on computation resource in the problem,we develop a much more ef?cient on-line DVS algorithm than the state-of-art algo-rithm, FA, by analyzing the property of busy period structure and critical task structure,which can derive the optimal control without relying on special physical parameter. At last, we summarize some useful hints for solving optimization problems ofDEDS.