代码之家  ›  专栏  ›  技术社区  ›  Jacob

连续断点调度算法

  •  1
  • Jacob  · 技术社区  · 15 年前

    我在这里迷路了。这是个问题,我认为它是NP难的。一个中心配备有数量有限的工人,这些工人具备以下条件:

    1. 每天3班,每班2人
    2. 每位员工连续工作5天,然后休息2天,每天只上一班

    所以问题是:如果中心每天都保持活跃并且有一个可行的时间表,我们需要多少工人?

    更新:

    谢谢你的回答。我最接近的(随机暴力算法)是:

    X       3       0
    1       0       3
    2       3       1
    2       1       3
    0       1       2
    0       2       1
    3       0       2
    

    我把问题简化成两人一组(0-3代表4组),希望得到一个可行的解决方案。 X

    4 回复  |  直到 5 年前
        1
  •  3
  •   mjv    15 年前

    正如问题中所表达的那样。
    这是因为这些数字不相加(或者更确切地说是“除以”)。

    • 每天正好3班
    • 每班2个工人
    • 工人工作 最大值 连续5天
    • 最低限度 连续两天

    随着最小和最大限定符的引入, 最少需要9名工人
    请注意,尽管9似乎是一个绝对最小值,但考虑到需要每周轮班42次(3*2*7),且工人每周最多轮班5次(5个工作日2个休息日=一周),鉴于连续工作和/或休息日的要求,不能保证9足够。

    我就是这么想的。。。

    为了让事情变得简单,我给除1号和9号工人以外的所有工人分配了一个最佳时间表,正好是5天上班,2天下班#1和#9工作更少。当然,许多其他的安排也会起作用(也许这就是OP在暗示NP完全问题时所感觉到的)。此外,时间表是这样的,每个人每周的时间表完全相同,但也可以改变(可能引入一些公平性,让所有工人每隔一段时间都有一个较轻松的一周,但顺便说一句,这可能会导致一些困难,尊重5个最长工作日的要求)。
    示例时间表显示了连续两周,以帮助查看连续的工作日或休息日,但如前所述,每个星期都是相同的。

                                  Max Conseq Ws   Min Conseq Rs
    Worker #1   RRWWWRW RRWWWRW         3              2
    Worker #2   WWWWWRR WWWWWRR         5              2
    Worker #3   WWWRRWW WWWRRWW         5              2
    Worker #4   WWWRRWW WWWRRWW         5              2
    Worker #5   WRRWWWW WRRWWWW         5              2
    Worker #6   WRRWWWW WRRWWWW         5              2
    Worker #7   RWWWWWR RWWWWWR         5              2
    Worker #8   RWWWWWR RWWWWWR         5              2
    Worker #9   WWRRRRW WWRRRRW         3              3
    
    Nb of Ws    6666666 6666666
    

        2
  •  2
  •   btreat    15 年前

    每天3班*每班2人*(每周7天/每人5个工作日)=8.4人(如果不选择兼职,则为9人)。

        3
  •  0
  •   Randy    15 年前

    3班x 7天=21

        4
  •  0
  •   Grembo    15 年前

    好吧-尽管你有答案,让我试试。

    有7种可能的员工日程安排,表示为(1)天&休息日(0)

    0011111 1100111 1110011 1111001 1111100 0111110

    我有一个每班每种类型的员工数量矩阵,这个数字是一个整数变量。我的优化模型是:

    受制于:总计(#员工计划*员工计划) = 每班所需人员

    计划的员工数为整数

    您可以将第一个约束中的=符号更改为>=。然后你会得到一个可行的解决方案与额外的工作人员。您可以在Excel中使用basic SOLVER addin解决此问题。

    比方说,我每天需要4名员工轮班,但我愿意容忍额外的员工。

    使用上述时间表的解决方案是:

    按计划类型列出的员工人数:0,2,0,2,0,2,0

    (换言之,附表1001111有2个,附表1111001有2个,附表11111 00有2个以上)

    当然,这不是唯一的解决方案。至少有6个其他解决方案,有两个额外的工作人员。约束编程将是一种更好更快的方法,因为通常会有许多可行的时间表。