运筹学进展

PDF
运筹学进展/2021/文章

研究文章b|开放获取

体积 2021 |文章的ID 8876990 | https://doi.org/10.1155/2021/8876990

Kimmo Nurmi, Nico Kyngäs 一个成功的三期元启发式方法求解轮班最小化个人任务调度问题",运筹学进展 卷。2021 文章的ID8876990 12 页面 2021 https://doi.org/10.1155/2021/8876990

一个成功的三期元启发式方法求解轮班最小化个人任务调度问题

学术编辑器:Panagiotis P. Repoussis
收到了 2020年9月16日
修改后的 2021年1月11日
接受 2021年1月16日
发表 2021年1月29日

摘要

劳动力调度过程包括三个主要阶段:工作量预测、班次生成和员工名册。班次生成是将确定的工作量尽可能准确地转换为班次的过程。最小化轮班人员任务调度问题(smpsp)是一个必须将一组具有固定开始和完成时间的任务分配给异构劳动力的问题。我们证明了所提出的三阶段元启发式方法可以成功地解决最具挑战性的smpstp基准实例。元启发式算法求解47个实例中的44个达到最优。与先前发表的方法相比,元启发式产生了最好的总体结果。这些结果是在解决一个更复杂的基于任务的轮班生成问题时产生的副产品。元启发式生成的结果与使用商业MILP求解器作为解决过程的一部分的方法相当。该方法适用于大型实际应用场景。应用领域包括清洁、家庭护理、警卫、制造和货物交付。

1.介绍

劳动力调度过程包括三个主要阶段:工作量预测、班次生成和员工名册(例如,参见:[1])。工作负载预测是根据已知和预测的事件确定工作负载的阶段。班次生成是将确定的工作量尽可能准确地转换为班次的过程。生成的班次构成了员工名册阶段的输入,在这个阶段,员工被分配到班次。

从实践角度看,劳动力调度过程既依赖于优化资源,也依赖于人力资源。它将组织联系在一起,优化流程并简化决策。一个轮班计划者应该考虑轮班工作的法律和人的方面。从员工的角度来看,轮班工作与社会和家庭生活的压力、健康问题、积极性和忠诚度有关。当班次生成和员工值班表的输入数据得到很好的验证时,通过应用相关的优化方法,可以在财务效率和员工满意度方面取得显著的收益。关于劳动力调度的一个很好的文献综述可以在[2].

班次生成阶段创建班次结构,包括班次中要执行的任务、任务和休息的时间以及班次所需的技能。班次的产生是基于在计划范围内工作的所需员工的不同数量或班次必须涵盖的任务。我们把这些问题称为以员工为基础和以任务为基础的轮班生成问题。

本文的主要贡献如下:(我)提出的三阶段元启发式方法可以成功地解决最具挑战性的smpstp基准实例(2)元启发式算法求解47个实例中的44个达到最优(3)与先前发表的方法相比,元启发式产生了最好的总体结果(iv)元启发式生成的结果与使用商业MILP求解器作为解决过程的一部分的方法相当(v)结果可以在解决更复杂的基于任务的换班生成问题时得到

本文的组织结构如下:首先,我们描述了班次最小化人员任务调度问题和基于一般任务的班次生成问题。然后,我们介绍一组最具挑战性的smpstp基准测试实例。我们描述了我们用来解决各种组合问题的三阶段元启发式。最后,我们给出了我们的计算结果,并将其与最知名的结果进行了比较。

1.1.相关工作

Musliu等人的研究是对基于员工的轮班产生问题的第一个主要贡献。[3.].他们提出了一个问题,即给定某一时期的劳动力需求,以及对可能的开始时间和轮班长度的限制,以及每个雇员每周平均工作次数的上限。必威2490Di Gaspero等。[4提出了一个以员工为基础的问题,其中最重要的问题是尽量减少不同班次的使用。基于员工轮班制的应用领域包括医院、零售商店和呼叫中心,在这些领域,可以根据客户到达的时间预测特定时间段所需的员工数量。

在基于任务的班次生成问题中,目标是创建班次并为这些班次分配任务,以便将员工分配到班次。应用领域包括清洁、家庭护理、警卫、制造和货物交付。任务型问题的第一个主要贡献是道林等人的研究。5].他们创建了一个主花名册,一个轮班和下班的集合,然后将一组任务分配给具有必要技能的人员,这些人员当天可以上班。Valls等。[6提出了一个模型,其中他们最小化了执行机器负载计划所需的工人数量。后来,Krishnamoorthy和Ernst [7介绍了一组类似的问题,他们称之为人员任务调度问题(PTSPs)。考虑到在某一天值勤的员工,统一服务计划将每项任务分配给有能力执行任务的员工,并指定开始和结束时间。

随后,Krishnamoorthy等人。[8]介绍了一种特殊情况,称为最小化班次人员任务调度问题(smpsp),其中唯一的成本是由于使用的人员(班次)的数量。Nurmi等。[9]定义了一般基于任务的班次生成问题(GTSGP),其中的任务是创建匿名班次,并为这些班次分配任务,以便员工可以分配到班次。

2.材料与方法

2.1.问题描述

最小化轮班人员任务调度问题(smptp)包括将一组具有特定开始和结束时间的任务分配给具有特定技能集和可用时间间隔的员工。目标是找到所有任务的可行分配,使所使用的员工数量最小化。这一目标的动机是,有大量的临时员工可用,而管理层希望尽量减少员工池的使用。

smpstp的正式定义如下:一组任务J= {t1、……tn}需要分配给一组不同类型的员工E= {e1、……e}在指定的规划范围内。任务的处理时间间隔t所要进行的是由一个时间表确定的,有固定的开始时间吗年代t完成时间ft。每个员工e有一系列的任务JeJe可执行。每个任务t有一组员工吗EtE可以携带t。所有集JeEt根据员工的技能/任务的技能要求和员工的可用性/任务的时间窗口来定义。目标是最小化执行给定任务集所需的员工数量。这个问题的数学公式首先在[8].

数字1显示了smpstp的一个简化实例。该实例和提出的解决方案具有以下特点:(我)规划期间分为18个时间段(2)任务数为14,员工数为7(用字母A到G表示)(3)任务的持续时间由相应矩形的长度给出(iv)能够执行任务的员工用矩形表示(v)颜色表示哪些任务属于同一班次(vi)执行班次的员工人数为6人(七)执行任务的员工用圆括号(employee)表示G没有任务)

smpstp的基本假设如下:(A1)不允许抢占任务(A2)任务之间不存在优先约束(A3)每个任务只处理一次,不中断每个员工一次最多只能执行一项任务

一般基于任务的班次生成问题(GTSGP)是创建匿名班次并为这些班次分配任务,以便将员工分配到班次。目标不是最小化执行给定任务集所需的员工数量,而是最大化可行(轮班、员工)对的数量。一双(年代e)被认为是可行的e能进行移位年代。这个问题的数学公式首先在[10].

GTSGP的动机来源于劳动力调度过程。在换班产生阶段,我们应该尽可能多地创建换班,以确保工作人员的名册能够完成。我们应该确保由此产生的班次可以由员工执行;也就是说,每个班次可以分配给一个员工,所有班次都分配给某个人,没有员工被分配到多个班次。在GTSGP的实际应用中,全职常设和临时雇员预计将承担全部工作量的100%。这与smpstp背后的理念相反。

smpstp是GTSGP的简化版本。尽管如此,Kroon等人在[11], smpstp在强意义上是np困难的,即使允许抢占任务(A1)。除(A2)外,GTSGP的假设与smpstp相同。GTSGP与smpstp在几个重要方面有所不同:(B1)没有明确给员工分配任务(B2)任务不及时固定(B3)任务可能具有移位局部优先级约束(B4)考虑任务之间的过渡时间员工有总工作时间限制(B6)员工有可用性限制

据我们所知,已经设计了八种重要和显著的解决方法来解决这个问题。Krishnamoorthy等。[8使用拉格朗日方法来解决大型SMPSTP实例。放宽任务分配约束,利用拉格朗日系数中的目标函数偏差,独立求解每个工人的问题。林和英[12]开发了smptp的三相启发式方法。他们使用简单但非常有效的构造启发式方法获得初始解,然后使用迭代贪婪启发式方法进行改进,该启发式方法在求解问题的MIP模型时用作初始上界。实验结果表明,该算法优于Krishnamoorthy等人的算法。

Smet等。[13]采用了两阶段建设性元启发式方法。在第一阶段,他们使用了三种建设性的启发式方法,在第二阶段,他们使用了一种混合搜索和优化方法。他们的方法是第一个将第一个smpstp基准集(请参阅下一小节)的所有实例求解到最优的方法。作者表示,他们的新算法保持了smptp的艺术状态。费奇和拉皮格[14使用约束编程,同时采用自顶向下和自底向上的方法。他们广泛的实验表明,他们的贡献显著地改进了简单的smpstp模型,使其能够与最著名的方法竞争。

Baatar等人。[15]开发了一个分支定界方案,该方案与两个基于列生成的方法和一个启发式算法结合使用,以创建一个有效的解决程序。作者证明,他们的方法比仅仅使用标准的商用MILP求解器(CPLEX)性能更好。Hojati [16提出了一种新的smptp贪心启发式算法。结果表明,与现有的求解方法相比,启发式算法的性能良好,并且具有快速求解大型实例的优势。作者指出,他的方法不像前面描述的其他方法那样需要商用MILP求解器。Niraj Ramesh等。[17]通过将问题分解为单独的子问题来解决问题,并开发了几种精确的启发式方法来解决由此产生的子问题。作者表示,尽管他们证明了有趣的理论结果,但他们的方法实际上很容易超越其他类似的精确方法,从而达到了预期。

Chirayil Chandrasekharan等。[18]改进了[12]并提出了一种基于分解的方法,其中使用精确技术求解子问题以达到最优。然后利用子问题的最优解构造整个问题的可行解。这些新特性不仅提高了解的质量,而且在提高算法的可扩展性方面发挥了关键作用。作者指出,该方法适用于大型现实场景的应用。他们的方法是第一个将第二个smpstp基准集(请参阅下一小节)的所有实例求解到最优的方法。此外,他们能够为来自第三个smpstp基准集的几乎所有实例生成最优解决方案(请参阅下一小节)。

对于一般任务型轮班生成问题,目前只发表了一种求解方法。这个问题直到最近才被Nurmi等人提出。[9].作者使用PEAST元启发式方法求解了[10].我们将在“三相元启发式”一节中深入了解元启发式。

2.2.smpstp基准实例

据我们所知,还没有发布过smpstp的实际基准实例。到目前为止,已经发布了三组人工基准实例。Krishnamoorthy等。[8]提供了137个smptp实例的第一个数据集。数据集称为KEB实例。实例由五个特征生成:雇员数量、任务数量、任务长度、紧密程度和多技能程度。紧度级别定义为所有任务的总长度占所有员工总可用性的百分比。当这个级别为100%时,任务可以完全覆盖员工可用的时间段。多技能水平被定义为每个员工能够胜任的任务总数的平均百分比。当该级别为100%时,每个员工都可以执行所有任务。从现在开始,我们将多技能级别称为任务技能级别。外换银行数据集中的员工数为22 ~ 422,任务数为40 ~ 2105。移位长度固定为1440。 The lengths of the tasks vary between 50 and 400. The tightness level is fixed to about 90%, and the skill level is either 33% or 66%.

Smet等。[13]生成了第二个包含十个实例的数据集,因为他们能够将所有KEB实例求解到最优状态。数据集称为SWMB实例。员工人数为44 ~ 153人,任务数为258 ~ 1577个。移位长度固定为1440。任务的长度为120或280。密闭性等级固定为90%左右,技能等级为20%或30%。必威2490Fages和lap [14]生成了包含100个实例的第三个数据集,因为KEB和SWMB实例对于寻找高质量的下界来说是微不足道的。这个数据集被称为FL实例。员工人数为62 ~ 948,任务数为71 ~ 1583。移位长度固定为1560。任务的长度为120或280。密封性等级固定在90%左右,技能等级固定在25%左右。必威2490有关三组数据的摘要载于[16].

为了简洁起见,我们不会解决这三个数据集的所有247个实例。有些实例很容易解决,并且本节前面描述的八种方法中的大多数在大多数实例上都表现良好。接下来,我们确定了三个数据集中最具挑战性的47个实例如下:KEB: Krishnamoorthy等的VAWA启发式[j]。8]无法找到最优解,由Lin和Ying的建设性启发式[12]比最优解决方案至少低5%,137个实例中有14个。SWMB:所有10个实例。FL: Hojati的贪婪启发式[16]无法找到最优解,或者Fages和lap的约束规划方法得到的解[14]至少比100个实例中的23个最优解决方案低3%。

1- - - - - -3.显示所选实例的特征。除了紧度和技能水平外,我们还定义了其他五个硬度指标。@AVG度量表示每个非空班次的估计平均任务数。任务数除以最小轮班数的下界。对于下界,我们使用[16]用Solyali的一般下边界法[19].除了任务技能水平,我们还定义了轮班技能水平,它描述了普通员工执行普通班次所有任务的资格,即:台盟 n/,在那里台盟=任务技能水平;n=任务数,和= Solyali下界。重叠级别是两个任务重叠的概率。为了计算概率,我们需要迭代所有任务对一次。


韩国外换银行# 选择 #是员工 #任务 @AVG 紧张程度 任务技能水平 轮班技能水平 重叠的水平 %我 @PAIRS

9 40 49 104 2.6 89.9 35.0 6.52 57.3 98.1 4.15
11 20. 24 119 6.0 90.0 36.2 0.24 26.0 96.6 0.90
45 60 67 420 7.0 90.0 33.9 0.05 24.1 97.9 0.92
59 59 70 525 8.9 91.4 34.4 0.01 19.4 96.8 0.83
75 60 72 665 11.1 90.0 34.2 0.001 15.4 98.2 0.88
77 160 180 688 4.3 90.0 33.4 0.87 36.8 99.0 2.77
79 80 94 689 8.6 90.1 33.6 0.01 19.8 99.4 0.99
80 99 112 691 7.0 90.9 33.8 0.05 24.4 99.4 1.03
89 70 88 788 11.3 90.1 34.0 0.001 15.3 98.6 0.86
94 80 93 881 11.0 90.0 33.8 0.001 15.6 98.9 0.89
98 80 91 896 11.2 90.0 34.2 0.001 15.3 99.2 0.94
106 One hundred. 121 1096 11.0 90.0 33.3 0.001 15.6 99.7 0.96
107 One hundred. 114 1112 11.1 90.0 33.7 0.001 15.4 99.8 0.96
108 128 162 1115 8.7 91.4 33.6 0.008 19.9 99.5 1.00

一行中的三个粗体值表示硬实例。

SWMB # 选择 #是员工 #任务 @AVG 紧张程度 任务技能水平 轮班技能水平 重叠的水平 %我 @PAIRS

1 40 50 258 6.5 89.6 19.5 0.003 25.6 91.9 0.63
2 40 44 510 12.4 87.6 19.6 0.000 13.3 93.5 0.58
3. 77 102 525 6.8 93.5 30.0 0.027 25.4 96.8 0.92
4 98 113 647 6.6 91.7 20.0 0.002 25.7 96.4 0.86
5 59 77 777 13.2 91.5 29.7 0.000 13.2 96.4 0.85
6 116 135 777 6.7 92.9 19.9 0.002 25.8 96.3 1.68
7 59 70 781 12.8 88.5 19.9 0.000 13.1 95.0 0.64
8 79 88 1022 12.8 90.0 19.9 0.000 12.8 96.0 0.65
9 98 125 1308 13.2 90.9 19.8 0.000 13.2 96.5 0.75
10 116 153 1577 13.6 93.1 19.9 0.000 13.6 95.8 0.66

一行中的三个粗体值表示硬实例。

FL # 选择(磅 #是员工 #任务 @AVG 紧张程度 任务技能水平 轮班技能水平 重叠的水平 %我 @PAIRS

5 30. 81 110 3.7 17.8 26.4 0.76 10.5 98.2 87.0
28 105 262 402 3.8 19.1 26.0 0.58 11.0 99.5 31.7
29 95 248 355 3.7 18.5 28.3 0.90 11.6 One hundred. 39.7
31 116 290 488 4.2 21.0 25.7 0.33 10.4 97.7 32.0
33 132 338 534 4.0 20.3 25.7 0.41 10.8 99.4 35.1
35 118 308 469 4.0 19.8 26.6 0.52 11.1 99.4 37.3
39 108 284 446 4.1 19.8 25.7 0.36 10.6 98.4 29.9
45 144 376 586 4.1 20.5 27.0 0.49 11.4 99.7 50.8
46 157 409 635 4.0 20.2 26.6 0.47 11.2 99.4 46.1
54 190 498 850 4.5 22.5 25.8 0.23 10.7 96.8 48.0
60 173 443 783 4.5 21.9 27.0 0.27 10.7 98.6 46.3
61 222 551 891 4.0 20.0 26.3 0.47 11.0 98.2 66.2
62 262 610 1096 4.2 20.8 25.5 0.33 10.2 99.0 64.8
63 203 524 905 4.5 21.9 26.5 0.27 11.1 98.1 56.4
64 140 366 570 4.1 20.2 26.2 0.43 11.0 99.1 43.8
68 219 561 958 4.4 21.4 27.3 0.35 11.0 99.3 66.0
69 211 550 891 4.2 21.1 26.1 0.34 10.8 99.3 62.8
77 248 648 1123 4.5 22.1 26.6 0.25 10.7 98.4 69.7
79 246 638 1052 4.3 21.0 26.3 0.33 10.8 99.4 74.1
80 222 578 885 4.0 19.6 27.0 0.54 11.2 99.5 77.5
84 247 644 1121 4.5 21.9 26.1 0.22 10.4 99.2 68.4
89 319 790 1371 4.3 21.0 25.6 0.29 10.5 99.6 82.3
94 313 812 1394 4.5 21.9 25.7 0.24 10.6 98.3 78.1

一行中的三个粗体值表示硬实例。

%ICH度量指示了在“三相元启发式”部分中描述的迭代建设性启发式可行地分配的任务的百分比。启发式最大化可行(轮班和雇员)对的数量,即解决GTSGP问题,如前所述。@PAIRS度量表示对每个非空班次的可行对的平均数量的估计。由迭代建设性启发式生成的可行对数除以Solyali下界。注意,启发式生成的GTSGP解决方案与最优方案相差甚远。%ICH和@PAIRS显示的值是10次运行中的最佳值。

回想一下,我们选择解决最具挑战性的情况。从这些例子的特点可以得出以下结论:(我)与大多数其他实例相比,FL实例每个班次的任务更少。部分由于这个原因,FL实例的转换技能水平也更高。这些应该会使问题更容易解决。(2)FL实例的紧性级别低于其他实例。这样就更容易解了。(3)必威2490大约一半的外换银行和SWMB实例具有高度重叠级别,这应该使它们更容易解决。(iv)对于SWMB实例,迭代建设性启发式可行分配的任务百分比(%ICH)较低,这可能使它们更难解决。从这个意义上讲,KEB和FL实例似乎同样容易(或很难)解决。(v)FL实例彼此非常相似。这将使它们同样难以(或容易)解决。

根据@PAIRS值,在KEB和SWMB实例中,几乎没有一个员工熟练地执行每个班次。对于FL实例,生成的解决方案将是这样的,许多员工可能会执行几个班次。这可以使FL实例更容易解决。

2.3.三阶段元启发式

我们创建了PEAST元启发式(参见,例如,[20.])来解决现实世界的调度问题。元启发式已经在商业上使用了好几年,例如,在员工名册和职业体育联盟的日程安排中。此外,我们还使用它来解决更多的学术问题,如平衡不完全块设计,平衡主客场作业和预作业的单轮循环锦标赛,休息日调度和约束最小休息问题。然而,应该清楚的是,尽管元启发式对几种问题类型可能很强大,但不能保证它对其他问题类型也能很好地工作。天下没有免费午餐定理[21]意味着不存在更优的优化方法。

最近,我们开始研究一个新的现实问题,这是GTSGP的一个应用。作为这个过程的一部分,我们创造了一种适合商业用途的解决方法。该方法基于PEAST元启发式。在之前的所有PEAST采用中,我们都使用了随机初始解决方案。我们没有发现任何证据表明复杂的初始解决方案可以改善结果。相反,随机初始解似乎会产生更好的结果,或者至少是同样好的结果。然而,由于运行时间的要求,单独使用PEAST对于最大的GTSGP实际实例来说太慢了。我们需要一个快速的启发式来生成非常好的初始解。请注意,在GTSGP的实际应用中,没有达到最佳(学术)解决方案不是问题。在优化过程之后,可能会出现新的任务,其中一些任务可能需要更改或删除。

我们使用简单的破坏和重建启发式(RRH)生成初始解决方案,类似于[22].伪代码如图所示2。破坏运算符从解中移除随机长度的相邻任务字符串。分配给现有解决方案的所有任务都以随机顺序处理。对于每个任务t,一个随机字符串,包含t除非移位包含t已经被移除。当删除的任务总数超过给定参数时,销毁操作符退出。再创建操作符将空闲任务一个接一个地添加到现有解决方案中各自的最佳位置。首先,所有空闲任务都是随机排序的。对于每个任务t,评估在位解中所有可行的加法位置。请注意,位置的概念取决于具体的问题。

对于GTSGP,一个职位是由一个直接前任决定的,例如,一个任务或一个雇员。注意,任务在GTSGP中可以有很宽的时间窗口;因此,轮班内的任务顺序不是预先确定的。在smpstp中,没有时间窗口,它在一个班次内固定任务的顺序。任务t然后添加到导致最佳目标函数值的位置,并有很小的机会跳过到下一个最佳位置。连续跳绳不受任何限制,所以t可能不会被分配,即使它有可行的加法位置。当所有空闲任务都处理完后,重新创建操作符退出。

通过生成废墟和重建启发式的初始解决方案,我们进一步加快了总体运行时间。初始解决方案是通过使用快速迭代建设性启发式(ICH)生成的,该方法基于[12].伪代码如图所示3(一个)3 (b)。这是在计算ICH测量%时在“三相元启发式”一节中提到的启发式。启发式将未分配的任务逐个分配到可分配的班次,直到所有任务都被考虑(步骤3)。当尝试分配任务时,我们选择没有员工和任务冲突且总累积处理时间最大的班次。一个重新分配过程(步骤5)被反复应用于分配每个未分配的任务到一个班次,直到所有的任务都被分配或循环存在。当尝试分配任务时t,我们选择shift年代没有员工冲突,并且当前与任务冲突的任务的总累积处理时间最少t。重新分配任务t转移年代,我们取消所有轮班任务年代与任务冲突t

PEAST元启发式尝试改进由废墟和重建启发式(以及迭代建设性启发式)生成的解决方案。在GTSGP的实际应用中,采用了PEAST元启发式(我)生成尽可能多的班次(2)确保工作人员的名册能够完成,使(3)考虑到名单的发布时间,计算时间仍然是可以接受的。

因此,我们不寻求最快可能的解决方法。出于我们的目的,使用更多的计算时间来实现更通用的移位是有利的。

PEAST元启发式的伪代码如图所示4。我们创建了PEASTP(参见,例如,[20.]),结合了六个著名的元启发式算法的特征:MH1,遗传算法;MH2,弹射链法;MH3,禁忌搜索;MH4,模拟退火;MH5,可变邻域搜索;MH6,破坏和重建方法。

这些元启发式的表现在科学上是合理的,并且在算法层面上进行了大量的实验研究。毫无疑问,它们为优化方法的宝库带来了真正的新颖性。通过结合并仔细调整科学有效的元启发式的最有效算子,经验丰富的启发式设计师可以有效地解决现实生活中的优化问题。如本节开头所述,有证据表明PEAST可以成功地解决不同的问题域。据我们所知,没有其他方法像PEAST那样结合了元启发式特征。

PEASTP在每个迭代(MH1)中使用一组解决方案。复制操作在一定程度上基于稳态复制:如果新解具有更好或相同的目标函数值,则新解取代旧解。此外,在给定的时间间隔内,将最差解替换为最佳解,即采用精英主义。弹射链搜索是PEASTP的核心。它探索了搜索领域中有前途的领域。弹出链搜索(MH2)扩展了一个基本的爬坡步骤,在一个步骤中生成一系列移动,从一个解候选到另一个解候选。出射操作符实际上实现了几个简单的局部搜索操作符来处理单个解决方案(MH1)。

通过引入禁忌列表改进了弹出链搜索,禁忌列表可以防止在相同的移动序列(MH3)中反向移动。采用模拟退火优化来决定是否在弹出链搜索(MH4)中提交一系列移动。这种细化不同于标准的模拟退火。它有三种用途。为了避免在有希望的搜索区域停留太长时间,采用了模拟退火优化和禁忌搜索。洗牌操作有助于从局部最优状态中逃脱。它们被用来将一个解扰动成一个可能更坏的解,以逃离局部最优(MH5)。使用与破坏和重建方法(MH6)相同的思想,洗牌之后进行几次弹出链搜索获得了更好的解决方案。

PEAST使用解的总体在每次迭代中。如果新解具有更好或相同的目标函数值,则新解立即取代旧解。此外,在给定的时间间隔内,将最差解替换为最佳解,即采用精英主义。PEAST使用传统的惩罚方法,对硬约束和软约束赋予正权(惩罚),并将违规分数求和,得到一个待优化的单一值。根据软约束的显著性赋予其固定的权值。然而,硬约束是使用一种独特的ADAGEN方法分配动态权重的。20.].

PEAST中的五个元启发式组件中的每一个都对生成高质量的解决方案至关重要。这在三个不同的问题领域得到了验证[20.].最近,求解GTSGP实例的结果[10结果表明,当其中任何一种成分被移除时,结果明显更糟。即使PEAST在没有任何组件的情况下运行的时间增加了一倍,结果也一样。

PEAST的实现发生了如此明显的变化,因此我们将新版本称为PEASTP。对数据结构进行了重新编码,并对弹射链搜索中代价函数的计算进行了更新。这些修改使我们能够并行化PEAST(因此是PEASTP),这反过来使我们能够解决比以前大得多的问题实例。尽管如此,在解决实际的GTSGP实例时,我们不能使用随机初始解。

3.结果与讨论

本节将介绍我们在前一节中介绍的smpstp基准实例的计算结果。结果与我们已知的所有其他最近smpstp解决方法的结果并列。回想一下,我们将实例解决为GTSGP实例,并且smpstp是GTSGP的一个相当简化的版本。因此,我们不仅优化了最少的班次,同时也产生了尽可能多的班次。也就是说,我们在解决更复杂的基于任务的轮班生成问题时,将smptp结果作为副产品生成。由于本文的目的,我们在这里只展示我们的smpstp结果,而不是实际的GTSGP结果。我们使用的PEAST版本与解决GTSGP实例时使用的相同。10].我们没有使用特定领域的知识来生成更好的解决方案,也没有进行任何参数微调。事实上,我们使用了与商业用途相同的版本,用于员工名册和体育日程安排。这些参数值已经在PEAST的几个早期实现和应用中得到验证,例如,参见[20.].

表格4显示前一节中描述的八种解决方案方法的已发布结果的摘要。三种求解方法是纯启发式方法:8], y14 [12], H18 [16].我们的结果显示在NK20栏中。其他五种方法使用商用MILP求解器作为求解过程的一部分:S14 [19], fl13 [14], b15 [15], r18 [17]和C20 [18].表格5显示详细的结果。



作者提供了详细的结果。彩色单元格上的值表示未求解到最优状态的实例的数量(如果适用,也可以求解到下限值)。


作者提供了详细的结果。绿色表示达到最优值。红色表示与最优值(或下限)的差异。白色表示结果尚未发表。

Chirayil Chandrasekharan等。[18]指出,在发布S14方法时,FL实例不可用,并且根据要求获得了S14结果的摘要。作者为我们提供了针对FL实例的S14方法的实例特定结果。

正如前面所解释的,我们使用尽可能多的计算时间来运行元启发式算法。对于实际的GTSGP应用程序,这可能需要几个小时,具体取决于规划周期的长短以及可用于计算的处理器和内核的数量。我们为每个基准实例运行了8小时的元启发式算法。由于我们正在解决GTSGP问题,所以当达到最佳smpstp值时,计算不会中断。为了获得最佳的GTSGP解决方案,我们需要为每个实例使用整个计算时间。测试是在一台标准的笔记本电脑上进行的,这台笔记本电脑是英特尔酷睿i7-8550, 1.8 GHz, 8gb内存,运行Windows 10。

结果表明,我们的三相元启发式算法可以成功地解决最具挑战性的smpstp基准实例。另一个观察结果是,我们的元启发式方法产生的结果与使用商业MILP求解器作为解决过程的一部分的方法相当。我们还可以说,与其他方法相比,我们的元启发式产生了最好的总体结果。元启发式算法求解47个实例中的44个达到最优。对于两个实例,我们的解决方案可能是最优的。只有一个例子表明我们的解决办法较差。

回想一下,我们选择解决最具挑战性的情况。显然,任务的数量和员工的数量对实例的硬度有直接的影响,因为它们扩大了搜索空间。更确切地说,当员工的平均任务数量增加时,组合搜索空间就会爆炸。因此,林和英[12指出具有较长任务长度的实例应该相对容易解决。Smet等。[13指出,较短的任务和较低的任务技能水平会使一个实例更难解决。

SWMB实例是基于这些观察结果生成的。Krishnamoorthy和Ernst [7表示,一个实例的密闭性应该接近90%,这样才具有挑战性。生成的FL实例使得重叠任务的最大数量不能为实例提供一个很好的下界[14].此外,与KEB实例相比,这些实例在每个任务中平均拥有更多的可用员工,但是它们在最优解决方案中使用这些员工的百分比要小得多。这将使实例更具挑战性。在所有比较的方法中,SWMB实例是唯一一个我们的方法没有产生最佳结果的实例集。

上述假设与我们在前一节给出的推理是一致的。基于我们的测试运行,我们可以相当安全地声明,低转换技能水平、低%ICH值和低@PAIRS值表示硬实例。因此,表中的粗体值1- - - - - -3.指定硬实例。请注意,粗体值是相对于同一数据集中的其他实例选择的。

一般来说,我们认为FL实例应该很容易解决,因为相当多的员工可能会进行几个班次。对于我们的元启发式算法,FL实例很容易解决,不包括实例FL#5和FL#89。对于这些情况,我们的解是一个高于下界值的解。这些解决方案很容易达成。因此,我们推测这两种情况下,下界值可能不是最优值。需要注意的是,在[18].

KEB实例很容易解决。实例具有最高的任务技能水平。此外,与FL实例的情况一样,KEB实例具有高百分比的由迭代建设性启发式分配的任务。

我们注意到swmb# 7实例对于我们的元启发式来说是非常困难的。我们目前对此没有结论。表格2表明swmb# 2实例应该至少同样难以解决。然而,对于我们的元启发式来说,这并不难。对于swmb# 7实例,除了元启发式的标准设置之外,我们还尝试了迭代构建启发式、破坏和重建启发式以及PEASTP的许多不同设置。我们甚至增加了运行时间。尽管如此,我们的运行时度量显示,我们甚至还没有接近到能够解决实例的程度。作为最后的实验,我们尝试使用Gurobi来改进我们的最佳解决方案。不幸的是,我们在7天的计算时间内没有找到更好的解决方案或证明解决方案是最优的。表格5结果表明,多达两种求解方法都成功地求解了该实例。此外,已发表的结果表明,解的生成速度相当快。

最后,我们记录了到达smpstp的第一个解决方案所花费的运行时间,同时我们继续在给定的计算时间内达到最佳的GTSGP解决方案。对于KEB实例,到达smpstp解决方案的中位数时间是0.9分钟。最小时间为0.001分钟,最大时间为9分钟。对于SWMB实例,相应的时间分别为86分钟、15分钟和207分钟,对于FL实例,相应的时间分别为0.7分钟、0.1分钟和19分钟。这证实了我们之前的讨论,SWMB实例应该是最具挑战性的实例。

4.结论

提出了一种基于三阶段元启发式的最小化班次人员任务调度问题。元启发式实际上解决了一个更复杂的基于任务的换班生成问题(GTSGP)。smpstp的结果是在求解GTSGP时产生的副产品。

在该方法的第一阶段,我们通过使用非常快速迭代的建设性启发式来生成初始解的种群。在第二阶段,使用破坏和重建启发式来改进解决方案。最后,并行化的PEAST元启发式算法使用解的总体来生成最终解。在之前的所有PEAST采用中,我们都使用了随机初始解决方案。然而,单独使用PEAST对于GTSGP的最大实际实例来说太慢了。这些实例的大小等于本文解决的最大smptp实例的大小。

GTSGP和smpstp实例的计算复杂度主要取决于任务的数量、员工的数量,尤其是每班平均任务的数量。这些值为PEAST方法的实际使用设定了限制。回想一下,我们只有几个小时来生成解决方案。我们的测试运行表明,当我们有超过1000个任务时,特别是当我们有几百名员工或每班平均任务数接近10个时,我们不能使用PEAST。在这些情况下,我们应该只使用ICH和RRH启发式。但是,这些解决办法在实际应用中仍然是可以接受的,因为在换班和工作人员名册完成后,肯定会出现新的任务,有些任务需要改变或取消。

我们在一台标准笔记本电脑上用8小时的计算时间解决了每个实例。我们的测试运行表明,对于高计算环境中的实际实例,这相当于两个小时。这需要使用具有大量处理器和核心以及非常快的内存的高性能计算机。考虑到整个劳动力调度过程和最终花名册的发布时间,两个小时是可以接受的。但是,运行时间明显高于同类方法的运行时间。

我们表明,所提出的三阶段元启发式方法可以成功地解决最具挑战性的smpstp基准实例。与先前发表的方法相比,元启发式产生了最好的总体结果。此外,元启发式生成的结果与使用商业MILP求解器作为解决过程的一部分的方法相当。这种比较并不完全公平,因为我们的方法花费更多的时间,但也解决了一个更复杂的问题。

元启发式算法求解47个实例中的44个达到最优。对于两个实例,我们的解决方案可能是最优的。只有一个例子表明我们的解决办法较差。我们还在研究剩下的两个FL实例是否可以解到下界。我们还将继续研究为什么SWMB实例中的一个对于我们的元启发式算法来说是极其困难的。确定原因有助于我们提高解决方法的通用性。我们可能会在一些简单的例子中遇到类似的结果,例如,那些不包括在我们的实验中的例子。

在不久的将来,我们将发布smpstp的第四个数据集。我们也会提出smpstp的扩展方案。

数据可用性

smpstp实例的数据在线可用。这三组数据可于[23(T. lapgue,“人事任务调度问题库”(在线)),可在https://sites.google.com/site/ptsplib/smptsp/instances(最后一次访问是2021年1月15日)。

利益冲突

作者声明本文的发表不存在任何利益冲突。

参考文献

  1. K. Nurmi和J. Kyngäs,“核心员工名册问题”,载于工程科学学报,第390-403页,世界科学出版公司,新加坡,2016。视图:出版商的网站|谷歌学者
  2. J. Van den Bergh, J. Beliën, P. De Bruecker, E. Demeulemeester和L. De Boeck,“人事调度:文献综述”,欧洲运筹学杂志,第226卷,第2号。3, pp. 367-385, 2013。视图:出版商的网站|谷歌学者
  3. N. Musliu, A. Schaerf和W. Slany,“对移位设计的局部搜索”,欧洲运筹学杂志,第153卷,第2号。1,第51-64页,2004。视图:出版商的网站|谷歌学者
  4. L. Di Gaspero, J. Gärtner, G. Kortsarz, N. Musliu, A. Schaerf,和W. Slany,“最小位移设计问题”,运筹学年鉴,第155卷,第155期。1,第79-105页,2007。视图:出版商的网站|谷歌学者
  5. D. Dowling, M. Krishnamoorthy, H. Mackenzie和D. Sier,“大型国际机场的工作人员名册”,运筹学年鉴,第72卷,第125-147页,1997。视图:出版商的网站|谷歌学者
  6. V. Valls, A. psamurez和S. Quintanilla,“将异质劳动力分配到给定时间表的图形着色模型,”欧洲运筹学杂志,第90卷,no。2,第285-302页,1996。视图:出版商的网站|谷歌学者
  7. M. Krishnamoorthy和A. T. Ernst,“人员任务调度问题”,载于优化方法及应用杨晓明,张国良,张国良,张国良。,卷。52,pp. 343–368, Springer, Boston, MA, USA, 2001.视图:谷歌学者
  8. M. Krishnamoorthy, A. T. Ernst和D. Baatar,“大规模轮班最小化人员任务调度问题的算法”,欧洲运筹学杂志, vol. 219, no。1, pp. 34-48, 2012。视图:出版商的网站|谷歌学者
  9. K. Nurmi, N. Kyngäs和J. Kyngäs,“劳动力优化:一般基于任务的轮班生成问题”,国际应用数学杂志,第49卷,no。4、2019。视图:谷歌学者
  10. N. Kyngäs, K. Nurmi和D. Goossens,“一般基于任务的轮班生成问题:公式和基准”,载于第九届多学科国际调度会议论文集:理论与应用(MISTA)2019年12月,中国宁波。视图:谷歌学者
  11. L. G. Kroon, M. Salomon, L. N. Van Wassenhove,“操作固定间隔调度问题的精确和近似算法”,欧洲运筹学杂志,第82卷,第2号。1,页190-205,1995。视图:出版商的网站|谷歌学者
  12. S.-W。林和k - c。“最小化人员任务调度问题的班次:一个三相算法,”欧洲运筹学杂志,第237卷,第2号。1, pp. 323-334, 2014。视图:出版商的网站|谷歌学者
  13. P. Smet, T. Wauters, M. Mihaylov和G. Vanden Berghe,“轮班最小化人员任务调度问题:一种新的混合方法和计算见解,”ω,第46卷,第64-73页,2014。视图:出版商的网站|谷歌学者
  14. J.-G。Fages和T. lapontgue,“用差分约束过滤AtMostNValue:应用于轮班最小化人员任务调度问题”,in约束规划的原理和实践, C. Schulte主编,第8124卷,第63-79页,施普林格,柏林,德国,2013年。视图:谷歌学者
  15. D. Baatar, M. Krishnamoorthy和A. T. Ernst,“班次最小化人员任务调度问题的基于三重的精确方法”,载于Algorithms-ESA, N. Bansal和I. Finocchi,编辑。,卷。9294,pp. 59–70, Springer, Berlin, Germany, 2015.视图:谷歌学者
  16. M. Hojati,“班次最小化人员任务调度问题的贪婪启发式”,计算机与运筹学, vol. 100, pp. 66-76, 2018。视图:出版商的网站|谷歌学者
  17. D. Niraj Ramesh, M. Krishnamoorthy和A. T. Ernst,“固定间隔调度问题的一些变体的有效模型、公式和算法”,载于数据和决策科学在行动, R. Sarker, H. A. Abbass, S. Dunstall等,主编。,pp. 43–69, Springer International Publishing, Cham, Switzerland, 2018.视图:谷歌学者
  18. R. Chirayil Chandrasekharan, P. Smet,和T. Wauters,“班次最小化人员任务调度问题的自动构造数学”,启发式杂志, 2020.视图:出版商的网站|谷歌学者
  19. O. Solyali,“班次最小化人员任务调度问题:一个有效的下限程序”,Hacettepe Üniversitesi İktisadi ve İdari Bilimler fak ltesi Dergisi,第34卷,no。2、2016。视图:出版商的网站|谷歌学者
  20. N. Kyngäs, K. Nurmi和J. Kyngäs,“解决现实世界调度问题的PEAST算法的关键组成部分”,载于软件工程课堂讲稿,第230-236页,世界科学,新加坡,2013。视图:出版商的网站|谷歌学者
  21. D. H. Wolpert和W. G. Macready,“优化没有免费的午餐定理,”IEEE进化计算汇刊,第1卷,第1期。1,第67-82页,1997。视图:出版商的网站|谷歌学者
  22. J. Christiaens和G. Vanden Berghe,“车辆路线问题的绳移除松弛诱导”,交通科学, vol. 14, 2019。视图:出版商的网站|谷歌学者
  23. T. lapautigue,“人事任务调度问题库”,2021,https://sites.google.com/site/ptsplib/smptsp/instances视图:谷歌学者

betway赞助版权所有©2021 Kimmo Nurmi和Nico Kyngäs。这是一篇开放获取的文章知识共享署名许可,允许在任何媒介上不受限制地使用、分发和复制,前提是正确引用原始作品。


更多相关文章

PDF 下载引用 引用
下载其他格式更多的
订购打印本订单
的观点698
下载657
引用

相关文章

年度文章奖:由本刊主编评选出的2020年度杰出研究贡献奖。阅读获奖文章