python - 使用 Python 为工作人员创建自动计划

Question

我正在尝试编写一个程序，该程序采用要填充的工作人员和槽的列表，以便为每个工作人员制定方便的时间表并填充所有槽。每个 worker 都有最大轮类次数(请注意， worker 不必连续轮类工作)，以及他们可以填补的空缺列表。如果所有插槽都未填充，程序将返回 False，否则它会生成分配给各个插槽的工作人员列表。

数据集和预期结果的模拟示例:

我尝试首先为由 (name, max_shifts, avail_slots) 初始化的工作人员创建一个类，然后创建一些 getter 方法。

Udon = ('Udon', 1, [3,4])
Ramen = ('Ramen', 1, [2])
Soba = ('Soba' , 2, [1,3])

Noodle-workers = [Soba, Ramen, Udon]
Slots = [1, 2, 3, 4]

Schedule(Noodle-workers, Slots) 

预计会返回:

Udon - 4 Soba - 3 Ramen - 2 Soba - 1

它们可以全部在列表或字典中，每一行可以是一个元组。结果的显示方式具有创造性的影响力。但如果插槽未填充，则函数返回 False

另外一个测试程序扩展性的数据集如下:

Erika  = Worker("Erika",   1, [1, 3, 7, 9])
Ryan   = Worker("Ryan",    1,   [1, 8, 10])
Reece  = Worker("Reece",   1,       [5, 6])
Gordon = Worker("Gordon",  2,    [2, 3, 9])
David  = Worker("David",   2,    [2, 8, 9])
Katie  = Worker("Katie",   1,       [4, 6])
Aashish= Worker("Aashish", 2,      [1, 10])
Grant  = Worker("Grant",   2,      [1, 11])
Raeanne= Worker("Raeanne", 2,  [1, 11, 12])
Erin   = Worker("Erin",    1,          [4])
Alex   = Worker("Alex",    1,          [7])

Workers = [Erika, Ryan, Reece, Gordon, David, Katie, Aashish, Grant, 
Raeanne, Erin] 
SLOTS = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

在 worker 列表中将 Erin (Workers[9]) 与 Alex 切换以获得所有槽的完整时间表

我的主要问题是打破概念来解决问题。我想到了一个树状结构来为 worker 产生所有可能的任务组合，然后消除那些不满足最大类次的任务。在有资格获得职位的两名 worker 之间进行选择时，这对我来说也是个问题。此外，我觉得生成递归可能会解决问题，但我不知道如何使用附带的结构来实现它以产生结果。

无论如何，如果这个问题能够得到解决以及解决它的概念，我将非常感激。

Answer 1

考虑一棵树，其中节点是分配问题本身(“ worker 列表”/“插槽列表”对)，边是单独的分配(“将乌冬面放在插槽 3 上”)。

在这里， worker 不仅仅是一个有名字的人，它是一个人连同相关的工作信息:剩余的类次，可用的槽位。

它是这样开始的:

然后可以进行深度优先搜索:

class Worker:

    def __init__(self, name, shifts, slots):
        self.name = name
        self.shifts = shifts
        self.slots = slots

    def copy(self):
        return Worker(self.name, self.shifts, self.slots[:])

    def assign(self, slot):
        assert slot in self.slots
        self.shifts -= 1
        self.slots.remove(slot)

def Schedule(team, slots):
    if slots == []:
        return {}
    for worker in team:
        if worker.shifts > 0:
            for slot in worker.slots:
                if slot in slots:
                    wcp = worker.copy()
                    new_team = [w if w != worker else wcp for w in team]
                    wcp.assign(slot)
                    assignments = Schedule(new_team, [s for s in slots if s != slot])
                    if assignments is not None:
                        assignments[slot] = worker.name
                        return assignments
    return None

Udon = Worker('Udon', 1, [3,4])
Ramen = Worker('Ramen', 1, [2])
Soba = Worker('Soba' , 2, [1,3])            

Noodle_workers = [Soba, Ramen, Udon]
Slots = [1, 2, 3, 4]

print(Schedule(Noodle_workers, Slots))

更新。一些解释:

• 列表理解:我使用它们并(可能)滥用它们，它们使创建列表的速度大大加快。请注意 if关键字在不同的位置，因为每一行使用不同的机制:

  • [w if w != worker else wcp for w in team] : 简单的列表理解 ( [expr(i) for i in ...] ) 结合三元运算符 ( a if b else c )

  • [s for s in slots if s != slot] : 条件列表理解 ( [expr(i) for i in ... if <condition>] .

• 扩展:提议的实现使用递归，其深度将等于要分配的槽数。如果这个数字很高，这可能是个问题。

• 目的new_team : 在开始之前，我将首先更详细地解释树模型。

  • 初始问题的定义是提供一个工作池和需要分配给他们的槽列表。

  • 每个 worker 的名字、他可以轮类的次数、他可用的空位列表都是特征的。

  • 当一个 worker 被分配到一个槽位时，我们必须更新他仍然可以工作的类次数，以及他仍然可用的槽位列表。这发生在 assign方法:

    self.shifts -= 1
    self.slots.remove(slot)
    

    我们还会从要分配的插槽列表中删除所选插槽。

  • 这又引出了一个新的分配问题:如何将剩余的 worker 分配到剩余的槽位？第一个 worker 的每个选择都会导致不同的新分配问题。新的分配问题是我们树结构中先前问题的子节点。

  • 在深度优先搜索过程中，如果一次搜索不成功，我们将不得不在树中向上退一步，继续循环遍历父节点中可能的赋值。

现在请注意，一个问题由 Worker 的列表组成对象(或 OP 代码中的列表)和插槽列表。在 python 中，列表和对象通过引用(指针)传递。如果在深度优先搜索的给定步骤中，一个 Worker对象被修改(因为一旦分配了该工作人员就必然会被修改)，当我们爬回树以探索其他分支时，该对象将保持修改状态，这会破坏代码。为避免这种情况，我们创建了每个要分配的 worker 的副本:

                wcp = worker.copy()

修改后将这个副本传给子节点。这样做我们可以保证当我们返回到该节点时不会损坏任何数据。

插槽列表也会出现同样的问题:如果我们通过 slots到子节点，在使用 slots.remove(slot) 删除插槽后, 如果一些子节点做同样的事情，列表 slots最终会被破坏，列表 team 也是如此。如果我们也这样做的话。

这是通过将新的工作人员列表和新的槽列表传递给子节点来解决的。