第九章：流水车间调度器

• 作者简介
• 流水车间调度器
• 背景
  • 流水车间调度
  • 局部搜索
• 通用求解器
  • 解析问题
  • 编译解决方案
  • 打印解决方案
• 邻域
• 启发式
• 动态策略选择
• 讨论

原文信息

本章翻译自 A Flow Shop Scheduler。

作者简介

Christian Muise 博士是 MIT CSAIL 的 MERS 组的研究员。他对各种主题感兴趣，包括 AI、数据驱动项目、映射、图论和数据可视化，以及凯尔特音乐、雕刻、足球和咖啡。

流水车间调度器

流水车间调度是运筹学中最具挑战性和研究最充分的问题之一。像许多具有挑战性的优化问题一样，对于实际规模的问题，找到最佳解决方案是不可能的。在本章中，我们考虑使用一种称为局部搜索的技术的流水车间调度求解器的实现。局部搜索允许我们在无法找到最佳解决方案时找到"相当好"的解决方案。求解器将在给定的时间内尝试找到问题的新解决方案，并在最后返回找到的最佳解决方案。

局部搜索背后的想法是通过考虑可能稍微更好的类似解决方案来启发式地改进现有解决方案。求解器使用多种策略来（1）尝试找到类似的解决方案，以及（2）选择一个有希望探索的下一个解决方案。该实现用 Python 编写，没有外部依赖项。通过利用 Python 的一些鲜为人知的功能，求解器在求解过程中根据哪些策略工作良好动态更改其搜索策略。

首先，我们提供有关流水车间调度问题和局部搜索技术的一些背景材料。然后我们详细查看通用求解器代码以及我们使用的各种启发式和邻域选择策略。接下来，我们考虑求解器用于将所有内容联系在一起的动态策略选择。最后，我们通过对项目的总结和通过实现过程学到的一些经验教训来结束。

背景

流水车间调度

流水车间调度问题是一个优化问题，我们必须确定作业中各种任务的处理时间，以便安排任务以最小化完成作业所需的总时间。例如，以具有装配线的汽车制造商为例，汽车的每个部分都在不同的机器上按顺序完成。不同的订单可能有定制要求，例如，使车身喷漆的任务因车而异。在我们的示例中，每辆车都是一个新作业，汽车的每个部分称为任务。每个作业都将具有相同的任务序列。

流水车间调度的目标是最小化处理所有作业中的所有任务到完成所需的总时间。（通常，这个总时间称为完工时间。）这个问题有许多应用，但最相关的是优化生产设施。

每个流水车间问题都由 $n$ 台机器和 $m$ 个作业组成。在我们的汽车示例中，将有 $n$ 个站点来处理汽车，总共要制造 $m$ 辆汽车。每个作业都由恰好 $n$ 个任务组成，我们可以假设作业的第 $i$ 个任务必须使用机器 $i$ 并需要预定的处理时间：$p(j,i)$ 是作业 $j$ 的第 $i$ 个任务的处理时间。此外，任何给定作业的任务顺序应遵循可用机器的顺序；对于给定作业，任务 $i$ 必须在任务 $i+1$ 开始之前完成。在我们的汽车示例中，我们不希望在组装框架之前开始给汽车喷漆。最后的限制是没有两个任务可以同时在一台机器上处理。

因为作业内的任务顺序是预先确定的，所以流水车间调度问题的解决方案可以表示为作业的排列。在每台机器上处理的作业顺序对于每台机器都是相同的，给定一个排列，机器 $i$ 中作业 $j$ 的任务被安排为以下两种可能性中的最晚的一个：

1. 作业 $j-1$ 中机器 $i$ 的任务的完成（即，同一台机器上的最近任务），或
2. 作业 $j$ 中机器 $i-1$ 的任务的完成（即，同一作业中的最近任务）

因为我们选择这两个值中的最大值，所以将为机器 $i$ 或作业 $j$ 创建空闲时间。正是这个空闲时间我们最终想要最小化，因为它会推动总完工时间变大。

由于问题的简单形式，任何作业排列都是有效解决方案，最优解决方案将对应于某个排列。因此，我们通过更改作业的排列并测量相应的完工时间来搜索改进的解决方案。在下文中，我们将作业的排列称为候选。

让我们考虑一个具有两个作业和两台机器的简单示例。第一个作业有任务 A 和 B，分别需要 1 和 2 分钟完成。第二个作业有任务 C 和 D，分别需要 2 和 1 分钟完成。回想一下，A 必须在 B 之前，C 必须在 D 之前。因为有两个作业，我们只有两个排列要考虑。如果我们在作业 1 之前订购作业 2，则完工时间为 5；另一方面，如果我们在作业 2 之前订购作业 1，则完工时间仅为 4。

请注意，没有预算空间来更早地推动任何任务。良好排列的指导原则是最小化任何机器在没有任务要处理的情况下留下的时间。

局部搜索

局部搜索是一种在最优解决方案太难计算时解决优化问题的策略。直观地说，它从一个看起来相当好的解决方案移动到另一个看起来更好的解决方案。我们不是将每个可能的解决方案都视为下一个关注的候选，而是定义所谓的邻域：被认为与当前解决方案相似的解决方案集。因为作业的任何排列都是有效解决方案，所以我们可以将任何混洗作业的机制视为局部搜索过程（这实际上是我们在下面所做的）。

要正式使用局部搜索，我们必须回答几个问题：

1. 我们如何选择初始候选解决方案？
2. 给定当前候选，我们如何生成邻域？
3. 给定邻域，我们如何选择要探索的下一个候选？

以下三节依次解决这些问题。

通用求解器

在本节中，我们提供流水车间调度器的通用框架。首先，我们有必要的 Python 导入和求解器的设置：

import sys, os, time, random
from functools import partial
from collections import namedtuple
from itertools import product
import neighbourhood as neigh
import heuristics as heur

##############
## Settings ##
##############
TIME_LIMIT = 300.0        # 运行求解器的时间（秒）
TIME_INCREMENT = 13.0     # 启发式测量之间的时间（秒）
DEBUG_SWITCH = False      # 为 True 时显示中间启发式信息
MAX_LNS_NEIGHBOURHOODS = 1000  # LNS 中要探索的最大邻居数

有两个设置应该进一步解释。TIME_INCREMENT 设置将用作动态策略选择的一部分，MAX_LNS_NEIGHBOURHOODS 设置将用作邻域选择策略的一部分。两者都在下面更详细地描述。

解析问题

作为解析过程的输入，我们提供可以找到输入的文件名和应该使用的示例编号。（每个文件包含许多实例。）

我们从读取文件开始解析，并识别分隔每个问题实例的行。我们直接解析数据，将每个任务的处理时间转换为整数并将其存储在列表中。最后，我们压缩数据以反转行和列，以便格式符合上面求解代码的预期。

编译解决方案

流水车间调度问题的解决方案包括每个作业中每个任务的精确时间。因为我们用作业的排列隐式表示解决方案，所以我们引入 compile_solution 函数将排列转换为精确时间。

打印解决方案

当求解过程完成时，程序以紧凑形式输出有关解决方案的信息。我们不是提供每个作业的每个任务的精确时间，而是输出以下信息片段：

1. 作业的排列
2. 完工时间
3. 每台机器的开始、结束和空闲时间
4. 每个作业的开始、结束和空闲时间

邻域

局部搜索背后的想法是从一个解决方案局部移动到附近的其他解决方案。我们将给定解决方案的邻域称为与其局部的其他解决方案。在本节中，我们详细介绍四个潜在的邻域，每个邻域的复杂性都在增加。

第一个邻域生成给定数量的随机排列。这个邻域甚至不考虑我们开始的解决方案，因此术语"邻域"有点夸大其词。但是，在搜索中包含一些随机性是一种好的做法，因为它促进了对搜索空间的探索。

对于下一个邻域，我们考虑交换排列中的任意两个作业。通过使用 itertools 包中的 combinations 函数，我们可以轻松地遍历每对索引并创建对应于交换位于每个索引处的作业的新排列。从某种意义上说，这个邻域创建的排列与我们开始的排列非常相似。

我们考虑的下一个邻域使用特定于手头问题的信息。我们找到具有最多空闲时间的作业，并考虑以每种可能的方式交换它们。我们取一个值 size，它是我们考虑的作业数：size 个最空闲的作业。该过程的第一步是计算排列中每个作业的空闲时间。

我们考虑的最终邻域通常称为大邻域搜索（LNS）。直观地说，LNS 通过孤立地考虑当前排列的小子集来工作——定位子集作业的最佳排列为我们提供了 LNS 邻域的单个候选。通过为特定大小的几个（或所有）子集重复此过程，我们可以增加邻域中的候选数量。

启发式

启发式从提供的候选集中返回单个候选排列。启发式还可以访问问题数据，以便评估哪个候选可能是首选的。

我们考虑的第一个启发式是 heur_random。此启发式从列表中随机选择一个候选，而不评估哪一个可能是首选的。

下一个启发式 heur_hillclimbing 使用另一个极端。它不是随机选择候选，而是选择具有最佳完工时间的候选。

最终的启发式 heur_random_hillclimbing 结合了上面的随机和爬山启发式。在执行局部搜索时，你可能并不总是想要选择随机候选，甚至是最好的候选。heur_random_hillclimbing 启发式通过以 0.5 的概率选择最佳候选，然后以 0.25 的概率选择第二佳候选，依此类推，来返回"相当好"的解决方案。

动态策略选择

局部搜索寻找良好排列的核心是使用特定的启发式和邻域函数从一个解决方案跳到另一个解决方案。我们如何选择一组选项而不是另一组？实际上，在搜索期间切换策略通常会有回报。我们使用的动态策略选择将在启发式和邻域函数的组合之间切换，以尝试动态转移到最有效的策略。对我们来说，策略是启发式和邻域函数（包括它们的参数值）的特定配置。

讨论

在本章中，我们看到了用相对少量的代码可以完成什么来解决流水车间调度的复杂优化问题。对于像流水车间这样的大型优化问题，找到最佳解决方案可能很困难。在这种情况下，我们可以转向局部搜索等近似技术，在无法找到最佳解决方案时计算足够好的解决方案。通过局部搜索，我们可以从一个解决方案移动到另一个解决方案，旨在找到高质量的解决方案。

局部搜索背后的一般直觉可以应用于广泛的问题。我们专注于（1）从一个候选解决方案生成相关解决方案的邻域，以及（2）建立评估和比较解决方案的方法。有了这两个组件，我们可以使用局部搜索范式在最佳选项太难计算时找到有价值的解决方案。

我们没有使用任何一种策略来解决问题，而是看到了如何动态选择策略以在求解过程中转移。这种简单而强大的技术使程序能够为手头的问题混合和匹配部分策略，这也意味着开发人员不必手工定制策略。