Stochastic Scheduling Methods for Queueing Systems

排队系统的随机调度方法

• 批准号: 9522795
• 负责人: MARK VAN OYEN
• 金额: $ 16.5万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-10-01 至 1999-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9522795&HistoricalAwards=false
• 关键词: Stochastic; Scheduling; Methods; Queueing; Systems

9522795 Van Oyen This research focuses on scheduling and release/admission control in systems for which the production process entails heterogeneous job types, service times, service delay penalties, and due dates as well as significant random variability in any or all of the following aspects: arrival process, job service times, and set-up overhead. In addition, the research develops models and methods of analysis for system control subject to incomplete observations of system state information. To achieve this, the research focuses on the development of an integrated analysis and design methodology to perform dynamic resource allocation for an extended class of polling models to address dynamic (state-dependent) control for queuing systems with incomplete state observations, set-up times/costs, and target production levels. The approach incorporates three core elements: (1) the characterization of optimal dynamic policies, (2) the computation of approximately optimal policies, and (3) the summary of insights gained from theoretical and numerical investigations in a set of operating principles for a class of problem instances. This research will culminate in the development of a methodology for the analysis and design of dynamia control algorithms for the control of queuing systems with incomplete state observations. Advanced scheduling and production control algorithms promise to yield significant performance advantages to manufacturing operations that employ them, provided they are built upon deeply rooted concepts. This research addresses a class of control problems in queuing networks that center on scheduling policies (and their interaction with release policies) for systems with significant switching (set-up) times and incomplete observation of the system state. The results from this research will impact a class of problems in resource allocation directly relevant to a broad range of manufacturing facilities. Moreover, the models, methods, and control algorithms developed will be u seful in emerging information networks and systems, which contain similar optimization issues.

本研究的重点是在生产过程中包含异构作业类型、服务时间、服务延迟惩罚和到期日的系统中的调度和放行/准入控制，以及在以下任何或所有方面的显著随机变化：到达过程、作业服务时间和设置开销。此外，本研究还开发了系统状态信息不完全观测下的系统控制模型和分析方法。为了实现这一目标，本研究侧重于开发一种集成分析和设计方法，为扩展类轮询模型执行动态资源分配，以解决具有不完整状态观察、设置时间/成本和目标生产水平的排队系统的动态（状态依赖）控制。该方法包含三个核心要素：(1)最优动态策略的表征，(2)近似最优策略的计算，以及(3)从对一类问题实例的一组操作原理的理论和数值研究中获得的见解的总结。这项研究将最终发展出一种分析和设计动态控制算法的方法，用于控制不完全状态观测的排队系统。如果先进的调度和生产控制算法建立在根深蒂固的概念之上，那么它们有望为使用它们的制造业务带来显著的性能优势。本研究解决了排队网络中的一类控制问题，该问题以调度策略（及其与释放策略的交互）为中心，用于具有重要的切换（设置）时间和不完全观察系统状态的系统。本研究的结果将影响与广泛的制造设施直接相关的资源分配中的一类问题。此外，所开发的模型、方法和控制算法在包含类似优化问题的新兴信息网络和系统中将是有用的。