8

I have been trying for some time solve a scheduling problem for a pool that I used to work at. This problem is as follows...

There are X many lifeguards that work at the pool, and each has a specific number of hours they would like to work. We hope to keep the average number of hours away from each lifeguards desired number of hours as low as possible, and as fair as possible for all. Each lifeguard is also a college student, and thus will have a different schedule of availability.

Each week the pool's schedule of events is different than the last, thus a new schedule must be created each week.

Within each day there will be so many lifeguards required for certain time intervals (ex: 3 guards from 8am-10am, 4 guards from 10am-3pm, and 2 guards from 3pm-10pm). This is where the hard part comes in. There are no clearly defined shifts (slots) to place each of the lifeguards into (because of the fact that creating a schedule may not be possible provided the availability of the lifeguards plus the changing weekly pool schedule of events).

Therefore a schedule must be created from a blank slate provided only with...

  • The Lifeguards and their information (# of desired hours, availability)
  • The pool's schedule of events, plus number of guards required to be on duty at any moment

The problem can now be clearly defined as "Create a possible schedule that covers the required number of guards at all times each day of the week AND be as fair as possible to all lifeguards in scheduling."

Creating a possible schedule that covers the required number of guards at all times each day of the week is the part of the problem that is a necessity and must be completely solved. The second half about being as fair as possible to all lifeguards significantly complicates the problem leading me to believe I will need an approximation approach, since the possible number of way to divide up a work day could be ridiculous, but sometimes may be necessary as the only possible schedule may be ridiculous for fairness.

Edit: One of the most commonly suggested algorithms I find is the "Hospitals/Residents problem", however I don't believe this will be applicable since there are no clearly defined slots to place workers.

4

2 回答 2

9

解决这个问题的一种方法是使用约束编程——维基百科文章提供了几种约束编程语言和库的链接。 这是一篇描述如何使用约束规划来解决调度问题的论文。

另一种选择是使用贪心算法找到（可能无效的）解决方案，然后使用本地搜索使无效解决方案有效，或者改进次优贪心解决方案。例如，首先为每个救生员分配他们喜欢的时间，这将导致为某些时段安排过多的救生员，也会导致为一些救生员分配的小时数荒谬；然后使用本地搜索从分配了太多守卫的插槽中取消分配时间最长的守卫。

于 2013-06-17T04:14:57.727 回答
4

你需要把你的公平标准变成一个目标函数。然后，您可以从任意数量的工作场所调度工具中进行选择。例如，您描述希望最小化期望时间和分配时间之间的平均差异。但是，我建议您考虑最小化最大差异。这似乎更公平（对我来说），它通常会导致不同的时间表。

然而，问题要复杂一些。例如，如果一名后卫总是被做空，而其他后卫都得到了他们想要的时间，那也是不公平的。因此，您可能希望在公平模型中引入变量，以代表前几周每个守卫的累积差异。此外，对于想要每周工作 4 小时的警卫来说，1 小时的差异可能比想要每周工作 20 小时的警卫更不公平。要处理这样的事情，您可能需要权衡差异。

您可能必须引入限制条件，例如没有分配超过一定小时数的警卫，或者每个警卫在轮班之间有一定的时间，或者每周分配给任何一名警卫的时隙数应该不超过某个阈值。许多调度工具具有处理这些约束的能力，但您必须将它们添加到模型中。

于 2013-06-17T04:13:48.670 回答