我一直在尝试解决一个与我曾经工作的游泳池有关的排班问题。问题如下:
这个游泳池有X名救生员,每个救生员都有特定的希望工作小时数。我们希望尽可能地让每个救生员的平均工作小时数与他们希望的小时数差距最小,并且对于所有救生员来说尽可能公平。每个救生员还是一名大学生,因此他们的可用时间表也不同。
每周游泳池的活动安排都与上周不同,所以必须每周创建一个新的排班表。
每天内有很多特定时间间隔需要救生员(例如:8am-10am需要3名救生员,10am-3pm需要4名救生员,3pm-10pm需要2名救生员)。这就是困难之处所在。没有明确定义的时间段可以放置每个救生员(因为根据救生员的可用性以及每周不同的游泳池活动时间表可能无法提供排班表)。
因此,排班表必须从白板开始创建,只提供以下信息...
- 救生员及其信息(期望小时数,可用性)
- 游泳池的活动时间表,以及每个时刻需要上班的救生员人数。
现在可以明确定义问题为“创建一个可能的排班表,以便在每周的所有工作日每时每刻都有所需数量的救生员,并且在排班中尽可能公平地对待所有救生员。”
创建一个可能的排班表,以便在每周的所有工作日每时每刻都有所需数量的救生员是必须完全解决的问题。然而,在排班中尽可能公平地对待所有救生员的第二部分显著地复杂化了问题,导致我认为我将需要一种近似的方法,因为将一天的工作时间划分成几种可能的方式可能是荒谬的,但有时这可能是必要的,因为唯一可能的排班表可能会因为公平起见而变得荒谬。
编辑:我发现最常被建议的算法之一是“医院/居民问题”,然而,我不认为这适用于本问题,因为没有明确定义的时间段可以放置工作者。