医疗诊所的最优作业调度

Question

我正在寻找以下问题的最佳解决方案。

我有3名初级医生(MO)和只有1名顾问。诊所在0800小时开始；总共有12名患者要看；最后一位患者理想情况下应该在1100小时开始预约。此外，所有3名主治医生必须在0800小时开始分别接诊1名患者。

每个病人都必须按以下顺序就诊:首先由一名医疗官(MO)看病，然后是咨询医生。病人可能会经历从看医生到看医生之间的等待时间(T)。

目的是缩短平均轮候时间(T)。那么，我们应该如何安排诊所呢？这个问题在附表中也有说明。

我怀疑这个场景可以被视为流水作业调度问题-所有建议的解决方案都将非常感谢。enter image description here

非常感谢！

Answer 1

这看起来像是Job Shop Scheduling的一种形式(因此在向外扩展时很难实现最优化，因为它是NP-complete/ hard )。您基本上是将每个工作(= 1个病人的1个预约)分配给一台机器(= 1个医疗官员)。最重要的是，您有工作依赖关系(因为同一天对患者的两次预约必须按一定的顺序进行)。

一种典型的方法是先构造启发式，然后进行局部搜索(例如禁忌搜索)。有一堆求解器可以帮助你用这样的算法来解决这个问题。例如，在Java语言中，有两个类似示例的OptaPlanner：Project Job Scheduling和Nurse Rostering。