Skip to main content
 首页 » 编程设计

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

2025年01月19日14jirigala

我正在尝试编写一个程序,该程序采用要填充的工作人员和槽的列表,以便为每个工作人员制定方便的时间表并填充所有槽。每个 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 之间进行选择时,这对我来说也是个问题。此外,我觉得生成递归可能会解决问题,但我不知道如何使用附带的结构来实现它以产生结果。

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

请您参考如下方法:

考虑一棵树,其中节点是分配问题本身(“ 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 也是如此。如果我们也这样做的话。

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