Large-Scale Fork-Join Networks with Synchronization Constraints

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

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.