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.

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