将人分配到病床 - 自动化的方法

Question

我每年都会帮助一个青年营.将参加者分配到卧室是一项艰巨的任务 - 有92间卧室,活动持续一周,与会者可以待上不同的时间,床需要重复使用.

目前需要一名志愿者〜一周时间将人员分配到房间.有很多规则可供遵循,因为并非所有与会者都会在整个一周内完成任务,而是在夜间进行.

我想自动完成任务.编程语言和计算成本是实现细节,我可以根据需要格式化输入数据/规则(包括代码生成).任何可以节省繁琐时间的东西......

可用的技术

我没有领域专业知识,所以首先我必须了解可能的方法.

约束编程似乎是明显的方法,因为有规则要遵循.但是规则不是二进制的,前一个线程向我介绍了软约束和成本函数.

当我阅读成本函数时,它指出了机器学习和神经网络.这些都很受欢迎,但我相信需要一组数据来训练它们,这是我没有的东西 - 我可以创建,但这需要花费更多的时间而不是手动分配.我已经知道了这些限制因素:我不必从数据中推断它们.

• 问:Prolog中的成本函数与机器学习中的成本函数不同吗？
• 问:机器学习是否适合这个问题？
• 问:我还忽略了其他方法吗？

我找不到在网上,期刊等讨论的房间分配问题; 它必须是常见的,因此我缺少一些特定于域的术语.对于需要它的医院和酒店,我确信它已经得到很好的研究.

• 问:文献中提到的床位分配问题是什么？

基于时间的作业

我也有一个概念性的问题.我可以看到我如何解决一个晚上,但我怎么想多个夜晚建模？

约束求解器(或其他技术)不知道时间(并且2016-09-05之前不会知道2016-09-06),但我需要输入人们住的夜晚并且每晚看到作业.

• 问:我应该如何考虑时间序列？

从概念上把握产出

第二个是:系统如何输出分配给哪些卧室的人？在Prolog数独求解器(例如)中,可以有多个解决方案,但这有很多约束.对于模糊约束,我最终会得到人X在房间Y中的概率,以及他们也在房间Z中的概率(如果你愿意的话,量子叠加)？

• 问:输出结果如何？

部分解决方案还可以

必须手动调整的首次通过分配将节省时间.就像手动分配"复杂"的参与者(如夜间安全,谁在特定房间睡觉)并让计算机完成其余工作一样.

• 问:这是否使问题更容易解决？

我的尝试

最初我想过从13年前复活我一个学期的Prolog知识,并为所有标准设置约束.这适用于一个非常简单的案例,但是一旦我超越了"必须"标准,我就失败了灰色规则和妥协.

示例规则(约束)

所有规则都有不同的优先级 为了简化我的分组must,should和nice.

• must 同房性别
  • 除非被"必须与之分享"选项(如夫妻)所覆盖
• must 需要残障人士客房的人可以获得
• must 如果与会者需要一个带婴儿床的房间,他们必须得到它
• must 指定"必须与X共享"或"必须与Y&Z共享"的与会者必须被分配到同一个会议室
  • 他们可能不会在相同的夜晚停留(例如,A-Thu停留,周二至周五为B).在整个期间阻止床是好的)
  • "必须共享"关系可以是单向的或双向的 - 我也可以实现
• must/should 如果与会者需要一个房间,他们必须得到它,除非没有可能的解决方案
• should按角色分组参加会议的与会者,例如"青年","青年领袖","厨师","领导者".有些角色比其他角色更适合混合.
• should尽量减少跳房:一旦你有一张床,整晚都待在这里.除非没有可能的解决方案
• should 情侣优先客房配有双人床
  • (我还没有弄清楚如何为此制定规则,这并不是假设所有"必须与之分享"的关系都是夫妻关系.目前它是用人类知识完成的)
• nice 他们参加的大学会议室的参加者(如适用)
• nice 优先考虑带有卫浴设施的房间,以及非青年角色

有更多的规则(例如,有饮食要求的人必须留在特定的建筑物中),但这提供了足够的例子.

每个房间的场地收费不是每个房间,所以尽量减少使用的房间数量并不重要 - 至少今年.

对餐厅和洗碗机的参加者必须进行类似的任务,但两者都要简单得多.

样本数据集

rooms:
    room1:
        building: Building1
        capacity: 2
        is_ensuite: yes
        has_cot: yes
    room2:
        building: Building2
        capacity: 4
        is_ensuite: no
        has_cot: yes
    room3:
        building: Building1
        capacity: 2
        is_ensuite: no
        has_cot: yes
    room4:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
    room5:
        building: Building1
        capacity: 4
        is_ensuite: no
        has_cot: no
---
people:
    albert:
        must_share_with: @brenda
        needs_cot: yes
        role: leader
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    brenda:
        role: no role
        gender: f
        arrive: 2016-09-06
        depart: 2016-09-09
    steve:
        role: student
        university: Cambridge
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    jason:
        role: student
        university: Bristol
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-09
    brian:
        role: tech
        gender: m
        arrive: 2016-09-05
        depart: 2016-09-10
    clare:
        role: speaker
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09
    george:
        role: band/after hours
        gender: m
        arrive: 2016-09-07
        depart: 2016-09-08
    sarah:
        role: band/after hours
        gender: f
        arrive: 2016-09-07
        depart: 2016-09-08
    john:
        role: band/after hours
        gender: m
        arrive: 2016-09-08
        depart: 2016-09-09
    janet:
        role: band/after hours
        gender: f
        arrive: 2016-09-08
        depart: 2016-09-09

样本结果

| Room  | Capacity | 2016-09-05 | 2016-09-06     | 2016-09-07     | 2016-09-08     | 2016-09-09     | 2016-09-10 | 
|-------|----------|------------|----------------|----------------|----------------|----------------|------------| 
| room1 | 2        | albert     | albert, brenda | albert, brenda | albert, brenda | albert, brenda | albert     | 
| room2 | 4        |            |                | jason, steve   | jason, steve   | jason, steve   |            | 
| room3 | 2        | brian      | brian          | brian          | brian          | brian          | brian      | 
| room4 | 4        |            |                | george         | john           |                |            | 
| room5 | 4        |            |                | sarah          | janet          |                |            | 

或者(这是否可以接受取决于哪些角色可以共享房间,例如乐队成员在凌晨3点睡觉,技术人员早上6点起床):

| Room  | Capacity | 2016-09-05 | 2016-09-06     | 2016-09-07     | 2016-09-08     | 2016-09-09     | 2016-09-10 | 
|-------|----------|------------|----------------|----------------|----------------|----------------|------------| 
| room1 | 2        | albert     | albert, brenda | albert, brenda | albert, brenda | albert, brenda | albert     | 
| room2 | 4        |            |                | jason, steve   | jason, steve   | jason, steve   |            | 
| room3 | 2        | brian      | brian          | brian, george  | brian, john    | brian          | brian      | 
| room4 | 4        |            |                | sarah          | janet          |                |            | 
| room5 | 4        |            |                |                |                |                |            |