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

Question

我试图写一个程序，需要一个工人和插槽列表来填补，拿出一个时间表，方便每个工人和填补所有的插槽。每个工人都有一个最大轮班数（请注意，工人不必连续轮班），以及他们可以填补的空缺列表。如果所有的槽都没有填满，程序将返回False，否则它将生成分配给各个槽的工作进程列表。你知道吗

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

我试着从为工人创建一个类开始（name，max\u shifts，avail\u 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]

将Erin（Workers[9]）与工人列表中的Alex切换，以获得所有插槽的完整时间表

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

不管怎样，如果这个问题能得到解决，我会非常感激的，还有解决这个问题的理念。你知道吗

Answer 1

考虑一个树，其中节点是分配问题本身（一个“工人列表”/“插槽列表”对），边是单独的分配（“在插槽3上放置Udon”）。你知道吗

在这里，工人不仅仅是一个具名的人，它是一个人连同相关的工作信息：剩余的班次，可用的空位。你知道吗

这是如何开始的：

深度优先搜索是可行的：

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的目的：在此之前，我将从更详细地解释树模型开始。你知道吗

  • 起始问题是通过提供一个工人池和一个他们需要分配到的槽的列表来定义的。

  • 每个工人都有自己的名字，他可以轮班的次数，他可以安排的时间。

  • 当一个工人被分配到一个时间段时，我们必须更新他仍然可以工作的班次，以及他仍然可以工作的时间段的列表。这种情况发生在assign方法中：

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

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

  • 这就引出了一个新的分配问题：如何将剩余的worker分配给剩余的槽？第一个工人的每一个选择都会导致一个不同的新分配问题。新的分配问题是树结构中前一个问题的子节点。

  • 在深度优先搜索期间，如果一个搜索不成功，我们将不得不在树中后退，继续循环父节点中可能的分配。

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

                wcp = worker.copy()

并在修改后将此副本传递给子节点。这样我们就可以保证当我们返回到那个节点时，不会有数据被破坏。你知道吗

插槽列表也会出现同样的问题：如果我们将slots传递给子节点，在使用slots.remove(slot)删除插槽之后，如果一些子节点做了相同的操作，那么列表slots最终会被破坏，如果我们做了相同的操作，列表team也会被破坏。你知道吗

这可以通过向子节点传递一个新的worker列表和一个新的slot列表来解决。你知道吗

Answer 2

嗨，克里斯托弗林斯，我真的很高兴向你展示我所做的一切。正如我所承诺的那样，我研究了您的代码，并在测试和调试过程中注意到，根据插槽列表的长度（即。辅助插槽不过，我是这么用getters的Worker.get\u插槽()). 排序非常重要的原因是，就像Erika有许多可能的槽一样，一旦她被分配到一个槽，她将无法填充一个关键的槽。因此，先用较少的选项来填补空缺，然后用更灵活的选项来填补剩余的空缺。它可能只是我的系统（2GB RAM，intel duo core），但运行你最初的代码时没有这种排序感觉就像是一个无限循环，特别是当我输入print语句以更好地理解你的工作时。你知道吗

我还注意到，错误的条件（即，当一个时间表完全无法实现时）在初始代码中进入了一个无限循环。也许它在你的系统上起作用，但我在你最后一篇文章后尝试了它，30分钟到一个小时的代码仍在运行，所以我尝试调整它，以确保当满足假条件时，代码结束。为此，我又添加了一个基本条件和一个中断条件。你知道吗

我非常感谢你，因为我想我从你的代码中学到了很多。下面代码的概念从许多方面受到您工作的启发。主要区别在于增加了基本情况，采用了我最近为edx在线课程学习的排序函数，最后使用了一个字典来显示适合给定槽位的所有worker。这意味着代码不必机械地按照列表的顺序跟随每个人，然后在移动到下一个工人之前将每个人填充到最大轮班数。我在您的初始代码中也观察到了这一点，我觉得跟踪插槽列表比跟踪工作人员更重要。你知道吗

这是修改后的代码。你知道吗

class Worker(object):
    def __init__ (self, name, shifts, slots):
        self.name  = name
        self.shifts = shifts
        self.slots = slots  # Slot is a list of available slots a TA can fill

    def get_name(self):
        return self.name

    def get_shifts(self):
        return self.shifts

    def get_slots(self):
        return self.slots

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

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

    def __str__ (self):
        return  self.name + ', max-shifts = ' + str(self.shifts) + ', slots = ' + '[' + ','.join(str(e) for e in self.slots) +']' 

def merge(left, right):
    ''' Helper function for the merge_sort function that follows'''
    result = []
    i,j = 0,0

    while i < len(left) and j < len(right):
        # This is the criterion merge_sort uses to sort the list argument
        # in this case I'll be sorting according to the length of list of slots for each Worker
        if len(left[i].get_slots()) < len(right[j].get_slots()): 
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1

    return result

def merge_sort(L):
    ''' This sorts any List according to the condition in the func above'''
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        left  = merge_sort(L[:middle])
        right = merge_sort(L[middle:])
        return merge(left, right)

def poss_assignments(team, slots):
    """
    creates a list of possible assignments for every available slot

    team - List of Workers
    slots - List of positive integer (slots)

    return - Dictionary with slots as keys and a list of Workers as values
    """
    poss_dict = {}
    poss_slots = slots[:]


    for i in poss_slots:
        val_list = []
        poss_dict[i] = val_list
        for t in team:
            if i in t.get_slots():
                poss_dict[i] += [t]  #replace with [t.get_name()]: Use this to see the names this func produces 

    return poss_dict

def Schedule(team, slots):
    team = merge_sort(team)
    if slots == []:
        return {}
    elif team == [] and slots != []:
        return print('No Workers to assign')

    possible_assignments = poss_assignments(team,slots) # A dictionary of slots with list of workers open for that slot

    accu_slot = slots[:]

    i = 0

    for slot in accu_slot:
       if slot in possible_assignments.keys():
           while i < len(possible_assignments[slot]):
               worker = possible_assignments[slot][i]
               wcp = worker.copy()
               wcp.assign(slot)

               new_slots = [s for s in slots if s != slot]
               new_team = [w if w != worker else wcp for w in team]

               assignment = Schedule(new_team, new_slots)

               if assignment is not 'Schedule unattainable.':
                   assignment[slot] = wcp.get_name()
                   return assignment
               else:
                   i += 1

       else:

           break

    return 'Schedule unattainable.'

#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]

#==============================================================================
Erika  = Worker("Erika",   1, [1, 3, 7, 9])
Ryan   = Worker("Ryan",    1,   [1, 8, 10])
Reece  = Worker("Reece",   2,       [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, David, Grant, Raeanne, Ryan, Reece, Gordon, Katie, Aashish]
Slots = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

#print(Schedule(Workers, Slots))
#print(Schedule(Noodle_workers, Slots))

请原谅我，如果代码没有出现正确的我仍然试图得到一个挂在这个论坛上张贴代码的缩进要求。你知道吗

无论如何，再次感谢，请帮我一个忙，用各种条件测试代码，比如空的workers列表，槽中有元素，反之亦然，槽中有一个数字，没有可用的worker来填充（例如，在可能的\u分配中有一个键，列表中没有worker，等等。再次感谢您的帮助。你知道吗