A Lower Bound for Minimizing Waiting Time in Coexisting Virtual and Physical Worlds

Abstract

To balance customer satisfaction across virtual and real-world interactions, we focus on enhancing service for dine-in customers at restaurants that typically prioritize online orders, such as those on Uber Eats. Utilizing three-agent scheduling strategies that adhere to each agent’s specific requirements—whether they are hard constraints or soft objectives—we effectively manage various types of orders, including immediate individual online orders, group reservations, and oral requests from dine-in customers. This approach significantly reduces waiting times and improves overall customer satisfaction. We propose a branch-and-bound algorithm with a tight lower bound based on preemption, which prioritizes agents A and B while reducing the total waiting time for agent C, representing dine-in customers. Computational experiments reveal that our algorithm significantly reduces total waiting times compared to existing two-agent scheduling strategies, demonstrating its effectiveness. Despite its efficiency, the algorithm incurs computational overheads, particularly with larger problem sizes. Our unique lower bound can be extended to other industries requiring multiple constraints or objectives. For example, in the film and television industry, real actors (represented by agent A) need to align their shooting times with 3D studios (represented by agent B) and stunt doubles for virtual avatars (represented by agent C) for scenes where they interact. That is, more agents are required to accommodate their constraints and objectives in such a scenario.

Keywords

• Multi-agent scheduling
• branch-and-bound algorithm
• lower bound
• waiting time
• completion time