多目标下位置分配的优化方法

《European Journal of Operational Research》：Optimization methods for assigning positions under multiple objectives

　　

•论文解决了实际的多目标优化问题。
•该问题出现在高等教育领域的职员岗位管理中。
•利用问题结构特性建立的 MIP 模型，带来了显著的速度提升。
•针对实际相关特例的快速组合算法。
•优化软件在合作伙伴处替代了繁琐的人工劳动。

引言

我们考虑了一个在特定（公共）机构招聘新职员时产生的优化问题，例如本项目的合作伙伴，慕尼黑工业大学（TUM）计算、信息与理工学院（SoCIT）。正如德国公共机构的惯例，招聘职员时有一组分配给该机构的固定岗位。这些岗位是行政单位，每个都有薪资等级和其他某些行政特征，每个员工被分配到一个或多个（部分）岗位中。我们指出，岗位既不明确指定可分配给它的员工角色（例如，“博士生”或“秘书”），也不指定他们的工作职责（例如，“应用数学研究”或“行政任务”）。特别是，员工的角色和职责对本论文完全无关紧要。相反，岗位可以被视为一种基金，可用于支付员工的薪资，最高至某个薪资等级。直观地说，组织用于职员的预算不是以金钱形式指定的，而是以具有固定特征的岗位形式存在的。

当招聘新职员时，需要将其分配到一个或多个岗位，甚至在整个合同期内可能不是分配给相同的岗位。给定的岗位可能被目前聘请的职员部分或完全占用，可能随时间不均匀变化，例如，因为其中一些只有固定合同（也许只是兼职）或他们暂时休产假。因此，可能需要随时间改变新职员对岗位的分配。当我们定义这种分配时，必须考虑几项规则和其他因素。新职员有一个薪资等级，每个选定岗位的薪资等级不得低于此。然而，它也不应该大太多，否则直观地说，差额对机构来说就损失了。更具体地说，如果将一个低薪资等级的员工分配给一个高薪资等级的岗位，那么机构就失去了将另一个高薪资等级的员工分配给该岗位的机会。此外，一些岗位在内部分配给大学的某些院系甚至院系内的组别。如果院系或组别招聘新职员，则应优先选择相应的岗位。独立于上述考虑之外，可用岗位具有某些额外的行政类别，出于行政原因，有时一个类别优于另一个。

更具体地说，对于新员工，我们需要决定她将分配给哪个（些）岗位，在哪个时间段，以及到什么程度，例如，全职当量的 50%。我们将每个岗位、时间间隔和程度（或高度）的这种组合称为一个块；见图 1 为例。新招聘可能需要一个以上的块。然而，出于行政原因，最好只使用少量块。这在新员工分配给可用岗位时产生了几项冲突的目标。在与 SoCIT 行政部门的同事进行充分讨论后，我们决定对这些目标进行字典序优化，因为这符合他们的需求。最高优先级是使用合适组别或院系的岗位，因为它们不能或不应用于其他目的。下一个优先级是尽可能好地匹配薪资等级编号，以最小化“损失”的差额。最低优先级涉及薪资等级字母，最后是最小化使用的块数。

这个问题可以看作是一个调度问题，在这个问题中，我们被分配具有某些不可用期的机器（岗位），我们寻求将一个作业（新职员）分配给它们。正如调度中常见的那样，我们允许迁移作业，即在一个机器上中断它并立即在另一个机器上恢复它。形象地说，迁移作业可以看作是在对应于调度的甘特图中将其“垂直”切割。在我们的案例中，我们也允许将其“水平”切割，并以此方式将其分布到不同的机器上，即几台机器同时执行作业的一部分。然而，在做这件事时，我们寻求将作业切割成只有少量的“片段”。这与最小化调度问题中的作业抢占次数有关。

如上所述，给定的岗位与组织内的任务角色并不是一一对应的。因此，新聘请的职员并不是为了以最好的方式适应可用的（纯行政）岗位而被选中的，而是根据工作概况，例如秘书、博士生或博士后。典型的情况是一位教授招聘一名新博士生，然后行政过程的一部分是为她找到可用岗位的分配，从 SoCIT 适合博士生的（大量）岗位池中选出。实际上，这种分配对教授和新聘请的职员是不可见的。由于 SoCIT 拥有大量具有不同薪资等级、行政特征和可用性等岗位，手工为新聘请的员工分配岗位将非常耗时，特别是如果寻求（近）最优解分配的话。

我们为将岗位分配给新职员的问题提出了混合整数线性规划（MIP）模型和一个组合算法。它们构成了我们为 SoCIT 行政部门同事开发的优化工具的核心，每当 SoCIT 招聘新员工时，他们都会定期使用它。

首先，我们提出了一个相对直接的我们问题的 MIP 模型。目标表示为具有四个条目的向量，我们以字典序优化它。其前三个条目可能获得分数值。因此，如果尝试用单个 MIP 优化向量，例如在目标函数中使用足够大的系数，可能会遇到数值问题。为了避免这种情况，一种自然的方法是连续解决四个数学规划问题，在我们的案例中是三个线性规划（LPs）和最后的一个 MIP。我们将这种方法作为基准测试的基线。然而，我们识别了我们问题的结构属性，允许我们推导出一个改进的模型，在其中我们可以用单个 MIP 解决整个问题，而不需要提到的 LPs。特别是，我们表明我们可以在预处理步骤中已经找到 MIP 的某些变量的正确值，因此，加速了 MIP 求解器。更准确地说，我们证明在任何最优解中，在某些天，某些岗位必须被选择，而其他岗位必须不被选择。此外，我们证明我们可以合并每个岗位可用程度相同的连续天数，这减少了我们的搜索空间。正如我们在基准测试中所示，这些改进大大加速了 MIP 求解器的运行时间。

然后，我们提出了另一个可以更快解决的 MIP 模型。直观地说，它是前一个 MIP 的简化版本。它仍然计算一个具有目标函数向量前三个条目最优值的解，但可能只为最后一个（最不重要的）条目提供次优值，即使 MIP 被最优求解。然而，我们在基准测试中表明，在实际实例上，通过这种方式我们通常仍然找到最优或近最优解，但运行时间比以前的方法好得多。

上述所有 MIP 模型都为每个岗位 i 和天 t 的组合使用一个变量，该变量表示岗位 i 在天 t 被分配的程度，例如，50%。相比之下，我们提出了一个不同的 MIP 模型，它使用块的变量，即编码某个岗位 i 在某个时间间隔内以某种程度 h 被使用的信息（形象地说是块的高度）。为了只引入有限（且小）数量的变量，我们不允许任意块高度，而是将自己限制在一个精心选择的 h 值集合和少量时间间隔上。为了确保我们的 MIP 保持可行，对于每一天，我们允许它选择比请求的总高度更大的块，例如，总共全职当量的 75%，即使新职员只有 50% 的岗位。我们证明，我们的 MIP 的最优解为给定实例最优解中的块数提供了一个下界。

在解决我们的 MIP 后，我们使用组合算法进行后处理例程，以消除这种过度分配。由此产生的解可能是次优的；然而，我们的基准测试表明，在实际实例上，它通常仍然找到非常好的解。此外，它甚至比我们的其他 MIP 模型更快。我们将此归因于一旦消除了所有平凡或重复的约束后，它只有非常少的约束；我们证明了剩余约束数量的上界。因此，这种 MIP 方法在运行时间和目标函数值之间提供了非常有利的权衡。

在许多实际实例中，最优解只使用少量块，即最多四个块。此外，通常最优解中选中的所有岗位都完美匹配新职员的薪资等级和其他行政特征，因为有足够多的这样的岗位可用。因此，我们提出了一个组合算法，用于计算这种实例的最优解。为此，我们证明对于那些实例，总是存在一个具有极少数可能组合结构之一中的最优解。我们的算法专门搜索具有这些结构的解，这被证明是非常快的。

我们用来自 SoCIT 同事的真实世界数据以及随机输入实例对我们的基于 MIP 的方法和组合算法进行了彻底的基准测试。我们的基准测试表明，我们对提到的第一个（直接的）模型的改进大大加速了运行时间。例如，在我们的真实世界数据集中，直接使用 Gurobi 的直接模型的运行时间超过 30 秒，使用 HiGHS 超过 6 分钟。即使使用我们改进的精确模型，使用 Gurobi 的平均运行时间也提高到约 4 秒，而使用我们更简单的 MIP，使用 HiGHS 平均甚至需要不到一秒。尽管后者 MIP 模型可能不会为每个实例找到最优解，但在我们的基准测试中，它仍然将 99.5% 的测试实例求解到最优性。我们基于块的 MIP 模型被证明甚至更快，并且在大多数情况下仍然找到最优或近最优解。最后，我们的组合算法在数据集中几乎所有可行的且适用它的实例上的运行时间小于 0.01 秒，并且它在这些实例的 100% 中找到可证明的最优解。

我们目标的一部分是最小化计算解中的块数。在调度术语中，这对应于最小化作业抢占次数。在实际调度应用中，抢占作业可能是昂贵的，因为它可能需要设置成本，如从硬盘加载数据或初始化机器。因此，寻求只有少量作业抢占的调度是自然的（另见 Albagli-Kim 等人，2016，Alon 等人，2021，Buttazzo 等人，2013，Shachnai 等人，2005）。我们相信我们的技术对于（其他）希望这样做调度问题可能是有用的。

例如，在我们的一个 MIP 公式中，我们简化了计算所得解中所用块数的计算，这在我们的基准测试中极大地加快了 MIP 求解器的速度。此外，在我们的基于块的 MIP 公式中，我们使用了一组精心选择的候选块以及一个合适的后处理例程，这使得在消除平凡或重复约束后，生成的 MIP 公式约束非常少，因此运行时间非常快。为了具体说明，在 2.1.1 节中，我们给出了一个可以使用我们的技术求解的调度问题的形式化定义，因为它构成了上述岗位分配问题的一个特例。我们的几个论断需要复杂的正式论证，尽管它们的证明思路相当直观。形式化证明可以在本文的补充材料中找到。

据我们所知，我们所考虑的岗位分配问题以前尚未被研究过。然而，如上所述，它可以被解释为一个调度问题，其中新员工是一个需要在给定机器上安排的单个作业，对应于我们的岗位。关于不同类型调度问题的文献非常丰富；我们参考 Leung (2004) 了解概述。在我们的设定中，由于之前的招聘，某些岗位可能不可用或仅部分可用。这类似于调度中给定机器的不可用期 (Ma 等，2010 年；Sanlaville 和 Schmidt，1998 年；Schmidt，2000 年)。例如，当机器暂时处于维护状态或被之前分配且无法移动的作业占用时，就会出现这种情况。关于给定机器具有不可用期的调度问题，有很多研究成果，例如，最小化单机上的完工时间 (Gawiejnowicz, 2007)，相同并行机 (Jaykrishnan 和 Levin, 2024, Mahjoub 等，2021)，无关机 (Santoro & Junqueira, 2023)，以及两机流水车间问题 (Allaoui 等，2006 年；Lee, 1999)。我们参考 Schmidt (2000)、Sanlaville 和 Schmidt (1998) 以及 Ma 等 (2010) 的综述，以了解该设定下的研究成果概述。我们注意到，在我们的问题中，机器也可能部分可用，例如，当之前的招聘者在某个时间间隔内占用了 100% 岗位中的 50% 时。

回想一下，在岗位分配问题中，我们可以将新员工同时部分分配到多个岗位。在调度中，这对应于在不同的机器上并行运行一个作业。Xing 和 Zhang (2000) 研究了该设定下的各种调度问题。通常，假设如果一台机器安排了一个作业（部分），则这台机器和这个作业需要固定的设置时间。Lee 和 Kim (2021)、Sar??i?ek 和 ?elik (2011) 以及 Tahar 等 (2006) 开发了适用于此场景的实用启发式算法。Shim 和 Kim (2008) 针对这种情况提出了一种分支定界算法。Correa 等 (2014) 给出了该设定下最小化完工时间（在无关机上）的近似算法。在岗位分配问题中，一个作业不仅可以同时分配到多个岗位，还可以从一个岗位重新分配到另一个岗位。在调度的背景下，这被称为作业迁移。允许这样做可以产生更好的解，正如 Chen 等 (2016) 和 Koren 等 (2000) 所示。作业迁移在实时调度设定中也很相关；这里我们参考 Davis 和 Burns (2011) 关于该主题的综述。

岗位分配问题的目标之一是最小化使用的块数。这与调度中最小化作业抢占和迁移的次数有关；这值得兴趣，因为它有时会产成成本。例如，Albagli-Kim 等 (2016) 考虑了一个调度问题，其中每个作业对于给定的值 k 最多可被抢占 k 次。Alon 等 (2021) 研究了以这种方式限制抢占次数的成本，并提供了一个渐近紧确界。Shachnai 等 (2005) 研究了一种调度设定，其中每个作业都有给定的最大允许抢占次数，以及一种变体，即寻求寻找具有最少作业抢占总数的最优调度。在实际场景中，抢占作业可能会产生运行时开销，从而导致调度延迟，如果可以的话，人们希望避免这种情况。这特别在实时系统领域被研究，例如，(Bertogna 和 Baruah, 2010, Bertogna 等，2011 年，Lee, 2017 年)。我们参考 Buttazzo 等 (2013) 关于这一研究方向的综述。

除了最小化块数之外，岗位分配问题还有三个其他子目标，因此它是一个多准则优化问题。关于调度和其他领域的多准则优化概述，我们参考 T'kindt 和 Billaut (2001)、Hoogeveen (2005) 以及 Nagar 等 (1995) 的综述。在我们的特定情况中，我们按字典序优化四个子目标。字典序目标函数在其他场景中也被研究过，例如，参见 Pasandideh 等 (2014)、Volgenant (2002)、Zhao 等 (2020)，以建立计算解的公平性属性 (Ogryczak 等，2014)。

章节摘要

岗位分配问题

每当招聘新员工时，她会签署一份具有特定期限和固定薪酬等级的合同。此外，还规定了就业是全职 (100%) 还是仅兼职到一定百分比，例如 50%。我们将此百分比称为员工的需求。然后，需要向她分配一个或多个岗位。可能，我们可能只向她部分分配这样一个岗位，例如，只占 50%，因为该岗位剩余的 50% 已经

组合算法

在许多实际查询中，最优解中的块数 w4* 相当小，例如 w4*≤4，并且需求 rt 在每一天 t∈T 上都是相同的。此外，在某些预处理步骤（例如，消除无关岗位）之后，岗位的向量 vi 通常是完全相同的。因此，在本节中，我们研究这样一个特例：对于任意两天 t,t′∈T，rt=rt′，并且对于任意两个岗位 i,i′∈I，vi=vi′。此外，我们假设给定的实例允许存在一个

整数规划公式

在第 3 节中，我们研究了所有天 t∈T 的需求 rt 相同且所有岗位 i∈I 的质量 vi 相同的特例。现在，我们研究我们问题的一般情况（无任何额外假设），并为它提出几种 MIP 公式。我们从一种相对直接的公式开始，然后提出三种额外的公式。

计算研究

我们使用来自 SoCIT 的真实数据集以及随机生成的数据对我们的基于 MIP 的方法和组合算法进行了基准测试。前者包含 1047 个单独岗位和 23 个不同的薪酬等级。为了模拟真实的工作流程，我们生成了 200 个随机查询，每个查询对应一名虚构的新聘员工，这产生了我们真实数据集中的 200 个实例。如同实际情况一样，一些岗位随后被自动排除，例如，

结论

在本文中，我们研究了为新员工分配岗位的问题，该问题出现在具有固定岗位集合的机构中供员工使用。结果表明，将问题建模为 MIP 的简单方法（如在 MIP-EXACT 中所做的那样）会产生相对较长的运行时间，特别是如果我们不使用 Gurobi 而改用非商业求解器 HiGHS 时。请注意，出于实际目的，拥有一个不依赖商业求解器的系统是理想的。

CRediT 作者贡献声明

Leon Jendraszewski：写作 – 审查与编辑，写作 – 初稿，可视化，软件，方法论，调查，形式化分析，概念化。
Andreas Wiese：写作 – 审查与编辑，写作 – 初稿，监督，项目管理，方法论，调查，形式化分析，数据整理，概念化。

竞争利益声明

作者声明他们没有已知的竞争经济利益或个人关系可能被认为影响了本文中报告的工作。

致谢

我们要感谢匿名审稿人的反馈以及许多有助于改进本文的有用建议。此外，我们要感谢 Richard Wolf 及其在 SoCIT 管理层的团队在整个项目过程中提供的出色的合作。

Leon Jendraszewski|Andreas Wiese