Large-Scale Fork-Join Networks with Synchronization Constraints

具有同步约束的大规模分叉连接网络

• 批准号: 1538149
• 负责人: Guodong Pang
• 金额: $ 25万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1538149&HistoricalAwards=false
• 关键词: Large; Scale; Fork; Join; Networks

Fork-join networks with synchronization constraints can be widely used to model patient flows in hospitals (e.g., emergency department treatment and patient discharge process) and data centers (e.g., parallelized Web search), among many other applications. In such networks, jobs are forked into parallel tasks to be served at service stations with parallel servers, and tasks are then joined for job completion or further processing provided that certain synchronization constraints are satisfied, for example, only completed tasks from the same job can be joined (non-exchangeable). However, very little is known about the performance, reliability and control of these networks, and existing methods in stochastic networks cannot be applied to study them. This award supports development of new methodology to better understand important performance measures (e.g., congestions and response times) of fork-join networks with non-exchangeable synchronization constraints, to design reliable fork-join networks with synchronization constraints operating in dynamic random environments, and to manage them in a cost-effective way. The research findings will have a broad impact on the society by improving the efficiency and quality of services in healthcare and data centers. The research will result in young STEM-trained graduates and underrepresented groups with new mathematical tools that help understand and improve the delivered services. The main mathematical challenge to study fork-join networks of multi-server service stations with non-exchangeable synchronization lies in the resequencing of arrival orders after service completion at each station due to randomness of service times. Unlike classical queueing networks, delay for synchronization is a key performance measure affecting system congestion, while resequencing is its determining factor. No analytical methods and results are known for such networks. This research will develop a new framework to solve the resequencing problem in fork-join networks, and thus, result in effective approximations for the synchronization dynamics as well as the service dynamics. The approach will use multi-parameter stochastic processes to study the service, queueing and synchronization dynamics, including sequential empirical processes driven by random vectors and their limits, and two-parameter processes tracking elapsed and residual service and wait times. Coordination and information sharing among parallel tasks of each job during their services will be exploited to develop optimal control policies for fork-join networks with synchronization constraints in order to minimize delay for synchronization as well as delay for service. Preventive strategies will be provided on the design and management of reliable fork-join networks with synchronization constraints operating in dynamic random environments.

具有同步约束的分叉连接网络可广泛用于对医院（例如急诊室治疗和患者出院流程）和数据中心（例如并行网络搜索）中的患者流进行建模以及许多其他应用。 在这样的网络中，作业被分叉成并行任务，由具有并行服务器的服务站提供服务，然后将任务连接起来以完成作业或进一步处理，前提是满足某些同步约束，例如，只能连接来自同一作业的已完成的任务（不可交换）。 然而，人们对这些网络的性能、可靠性和控制知之甚少，并且随机网络中的现有方法无法应用于研究它们。该奖项支持开发新方法，以更好地理解具有不可交换同步约束的分叉连接网络的重要性能指标（例如拥塞和响应时间），设计在动态随机环境中运行的具有同步约束的可靠分叉连接网络，并以经济有效的方式管理它们。研究结果将通过提高医疗保健和数据中心的服务效率和质量对社会产生广泛影响。该研究将为年轻的 STEM 培训毕业生和代表性不足的群体带来新的数学工具，帮助理解和改进所提供的服务。研究具有不可交换同步的多服务器服务站的分叉连接网络的主要数学挑战在于，由于服务时间的随机性，每个服务站服务完成后到达订单的重新排序。与经典排队网络不同，同步延迟是影响系统拥塞的关键性能指标，而重排序是其决定因素。此类网络尚无已知的分析方法和结果。这项研究将开发一个新的框架来解决分叉连接网络中的重新排序问题，从而对同步动态和服务动态产生有效的近似。该方法将使用多参数随机过程来研究服务、排队和同步动态，包括由随机向量及其限制驱动的顺序经验过程，以及跟踪已用和剩余​​服务和等待时间的双参数过程。将利用每个作业在其服务期间的并行任务之间的协调和信息共享来开发具有同步约束的分叉连接网络的最优控制策略，以最小化同步延迟和服务延迟。将针对在动态随机环境中运行的具有同步约束的可靠分叉连接网络的设计和管理提供预防策略。