Optimization for Systems Under Uncertainty: Modeling, Asymptotic Analysis, and Recursive Algorithms

不确定性下的系统优化：建模、渐近分析和递归算法

• 批准号: 9877090
• 负责人: Gang George Yin
• 金额: $ 12万
• 依托单位: Wayne State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2003-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9877090&HistoricalAwards=false
• 关键词: Optimization; Systems; Under; Uncertainty; Modeling

Proposal Title: Optimization for Systems under Uncertainty: Modeling, Asymptotic Analysis, and Recursive AlgorithmsProposal Number: DMS-9877090PI: G. George YinAffl.: Department of Mathematics, Wayne State University, Detroit, MI 48202 Tel. [phone], Fax [phone], Email: [e-mail] Description:Focusing on modeling and optimization for systems under uncertainty, thisproposal consists of four parts. Part I proposes two types of algorithms. Thefirst one is an approximation of an analog diffusion machine; the secondone also takes measurement errors into consideration. Our goal is to developasymptotic properties of such algorithms. By using weak convergence methods,suitably scaled sequences will be shown to converge to appropriate diffusions.Part II treats a class of hybrid models. Approximation schemes forsystems involving singularly perturbed Markov chains with weak and stronginteractions will be developed, which are useful for natural time-scaleseparation and reduction of complexity for large-scale systems.Part III investigates asymptotic properties of solutions of Cauchy problemsarising from null-recurrent diffusions. Our focus is on obtaining convergenceand rate of convergence of the solutions. One of the primary motivations comesfrom the investigation of singularly perturbed systems. The results will beuseful to the ever expanding applications in optimization, controlled Markovsystems, hierarchical decision making, production planning, telecommunication,queueing networks, and system reliability.Part IV models single-machine scheduling problems under random processing time, and/or under random machine breakdownsand repairs, and/or subject to random compression of processing times.Our objectives are to develop feasible models and to obtain optimalscheduling policies for the underlying systems. These results will allow usto design scheduling models and strategies for more complex jobshops byconsidering integrated processes as single-machine systems.Nontechnical explanation:To bridge the gap between theory and applications, this research projectincludes three components: modeling, asymptotic analysis, and simulation.The ultimate goals are to provide useful models, to investigate their basicproperties, and to develop sound and feasible algorithms.Part 1 proposes two classes of algorithms with applications to machinelearning,image segmentation, and various global optimization tasks.To meet the increasing demand on robust design and control of systems inspeechand pattern recognition, signal processing, telecommunications, andmanufacturing, Part 2 aims to reduce the complexity of a large-scalesystem of complex structure by using a simple system via approximationschemes.The origin of the planned work for Part 3 stems from the effort of modelinguncertainties due to random influence such as demands for a product in amanufacturing system or fluctuation in the stock market. To controlthe underlying system, it is imperative to understand the system's long-termbehavior, which is our primary goal.In production planning, it is vital to provide good strategyin sequencing the parts to be processed by the machines. Part 4 proposessingle-machine scheduling models in uncertain environment.The proposed work aims to develop optimal scheduling policies.The overall planned work represents a continuation of the PI's recent preliminary exploration in these areas. It is expected that the results will be applicable in the further improvements of optimization methods.

提案题目：不确定性下系统的优化：建模、渐近分析和递归算法。提案号：DMS-9877090PI: G. George YinAffl。摘要：本文主要研究不确定系统的建模与优化问题，主要分为四个部分。第一部分提出了两类算法。第一个是模拟扩散机的近似；第二种方法也考虑了测量误差。我们的目标是发展这种算法的渐近性质。利用弱收敛方法，证明了适当尺度序列收敛于适当扩散。第二部分讨论了一类混合模型。本文将发展具有弱和强相互作用的奇异摄动马尔可夫链系统的近似格式，这对于大规模系统的自然时标分离和降低复杂性是有用的。第三部分研究了由零循环扩散引起的柯西问题解的渐近性质。我们的重点是得到解的收敛性和收敛率。其中一个主要的动机来自于对奇异摄动系统的研究。研究结果将有助于优化、可控马尔可夫系统、分层决策、生产计划、电信、排队网络和系统可靠性等领域不断扩大的应用。第四部分模拟了随机加工时间下的单机调度问题，和/或随机机器故障和维修，和/或受制于随机压缩的加工时间。我们的目标是开发可行的模型，并获得底层系统的最佳调度策略。这些结果将允许我们通过将集成过程视为单机系统来为更复杂的作业车间设计调度模型和策略。非技术解释：为了弥合理论与应用之间的差距，本研究项目包括三个组成部分：建模，渐近分析和仿真。最终目标是提供有用的模型，研究它们的基本性质，并开发合理可行的算法。第1部分提出了两类算法及其在机器学习、图像分割和各种全局优化任务中的应用。为了满足语音模式识别、信号处理、电信和制造业对系统鲁棒设计和控制日益增长的需求，第2部分旨在通过近似方案使用简单系统来降低复杂结构的大型系统的复杂性。第3部分计划工作的起源源于由于随机影响（如制造系统中产品的需求或股票市场的波动）而产生的不确定性建模的努力。为了控制底层系统，必须理解系统的长期行为，这是我们的主要目标。在生产计划中，为机器加工的零件排序提供良好的策略是至关重要的。第四部分提出了不确定环境下的单机调度模型。提出的工作旨在制定最优调度策略。总的计划工作是PI最近在这些地区进行的初步勘探的继续。研究结果对优化方法的进一步改进具有一定的参考价值。