文件名称：加班在线提前排班：一种原始对偶方法-研究论文
文件大小：1.12MB
文件格式：PDF
更新时间：2024-06-29 12:56:20
advance scheduling; online resource
我们研究了服务操作中的一个基本在线资源分配问题，其中服务时间和奖励不同的异构到达流从有限数量的服务器/提供商发出服务请求。 这是一个在线对抗环境，其中对客户的到达过程一无所知。 每台服务器的常规容量有限，但可以以加班成本为代价进行扩展。 在每个客户到达时，系统在受容量限制的调度范围内选择服务器和服务时间。 该系统寻求易于实施的在线策略，允许竞争比率 (CR)，保证最坏情况下的相对性能。 在学术方面，我们针对上述问题提出了具有理论 CR 的在线算法。 在实践方面，我们研究了我们的方法和模型在来自合作伙伴医疗系统的预约安排数据上的实际适用性。 我们开发了新的在线原始对偶方法，不仅为每个到达的客户做出服务器日期分配决策，而且还为每个服务器在一个范围内的每一天做出加班决策。 我们还得出了一个竞争分析来证明理论上的性能保证。 我们的在线政策 (i) 对未来信息稳健，(ii) 易于实施且计算效率极高，以及 (iii) 接受理论 CR。 将我们的在线策略与离线最优策略进行比较，我们获得了一个 CR，它保证了我们的在线策略在最坏情况下的性能。 我们通过使用来自 UMHS 的真实约会调度数据来评估我们的在线算法的性能。 我们的结果表明，所提出的在线策略的性能比其理论 CR 好得多，并且大大优于普遍的先到先服务 (FCFS) 和嵌套阈值策略 (NTPO)。