CP还是DP？为何不兼得：部分车间调度问题案例研究

# CP或DP？为何不两者兼用：部分车间调度问题的案例研究

来源：https://arxiv.org/html/2605.23569

ICTEAM, UCLouvain, Belgium  
emma\.legrand@uclouvain\.be  
https://orcid\.org/0009\-0000\-3836\-1782

ICTEAM, UCLouvain, Belgium  
roger\.kameugne@uclouvain\.be  
https://orcid\.org/0000\-0003\-1809\-9822

ICTEAM, UCLouvain, Belgium  
pierre\.schaus@uclouvain\.be  
https://orcid\.org/0000\-0002\-3153\-8941

\CopyrightEmma Legrand, Roger Kameugne, and Pierre Schaus

\ccsdesc[100]Mathematics of computing Combinatorial optimization

\supplementdetails[subcategory=Source Code, swhid=...]Software  
https://anonymous\.4open\.science/r/DP\-CP\_JobShop\-8C5E

\EventEditorsJohn Q. Open and Joan R. Access  
\EventNoEds2  
\EventLongTitle42nd Conference on Very Important Topics (CVIT 2016)  
\EventShortTitleCVIT 2016  
\EventAcronymCVIT  
\EventYear2016  
\EventDateDecember 24–27, 2016  
\EventLocationLittle Whinging, United Kingdom  
\EventLogo  
\SeriesVolume42  
\ArticleNo23

###### 摘要

动态规划（DP）和约束规划（CP）是求解组合优化问题的成熟范式。通常，这两种方法被分开使用。本文旨在展示两者可以有效且优雅地结合，其中DP作为主要搜索框架，而CP作为子程序利用全局约束传播。本文针对部分车间调度问题（PSSP）提出了这样一种方法，该问题已有纯DP方法提出，并且有高效的CP过滤算法可用。PSSP是一个通用的调度问题，其中每个作业由一组具有任意优先级约束的操作组成。该方法足够灵活，可以容纳任何时间DP策略，例如任何时间列搜索，而原始DP算法以严格的逐层方式运行。此外，CP建模的灵活性使得合并任意优先级约束变得简单。因此，该模型自然处理任何优先级图，甚至能够设计大规模邻域搜索（LNS）方案，其中重用DP模型，并在重启之间施加偏序调度以改进当前解。虽然在这个特定问题上与最先进的纯CP求解器不具有竞争力，但我们的主要贡献是证明了这种混合集成的可行性。

###### 关键词：部分车间调度问题，动态规划，决策图，约束规划，大规模邻域搜索

###### 类别：\relatedversion

## 1 引言

本文考虑使用动态规划（DP）、约束规划（CP）以及混合DP-CP方法求解*部分车间调度问题*（PSSP）。PSSP是一个通用的调度问题，其中每个作业由一组具有任意优先级约束的操作组成。在[HookerH18]中，作者回顾了CP与运筹学（OR）的集成以求解组合优化问题。PSSP概括了经典的调度问题，如作业车间调度问题（JSP）和开放车间调度问题（OSP），这些问题是运筹学、人工智能和管理科学中广泛研究的组合优化问题[XiongSRH22, DauzerePeresDST24, pinedo2016scheduling, blazewicz2001scheduling, zhang2019review]。它们的持续相关性源于它们作为众多现实工业环境中调度问题的松弛或泛化。在这些问题中，一组操作必须在不同的机器上调度，并受给定的优先级约束。共同的目标是最小化制造周期，定义为所有操作的最大完成时间。这些调度问题通常是强NP难的[GareyJS76, GonzalezS76]，并在文献中得到了广泛研究[XiongSRH22, DauzerePeresDST24, GromichoHST12, HoornNOG17, Ozolins19, Ozolins20, Ozolins21, zhang2019review]。尽管对这些问题的精确方法进行了广泛研究，DP方法仍然相对罕见。对于JSP，Gromicho等人[GromichoHST12]引入了一种DP公式，将解视为操作序列，并应用特定技术来保持最优性保证。通过利用优势属性修剪搜索空间，该算法成功求解了中等规模的实例。Hoorn等人[HoornNOG17]后来改进了这种方法，证明了其能够从已建立的基准[vanHoorn]中找到特别困难实例的最优解。基于这一DP公式，Ozolins[Ozolins20]提出了一种改进的有界变体，将DP与分支定界结合，并在中等规模实例上进行了实验。纯CP方法结合了著名的NoOverlap全局约束[vilim2007global]和特定的搜索策略[baptiste2001constraint, LaborieRSV18]。为了在搜索树的每个节点实现最大域过滤，该全局约束集成了多种传播技术：*过载检查*、*边寻找*（也称为*首尾调整*[carlier1994adjustment]或立即选择[brucker1994job]）、*可检测优先级*和*非最先/非最后*规则。CP求解器可用于通过在大规模邻域搜索（LNS）框架内放松一部分赋值来迭代改进当前解，然后通过*失败定向搜索*[vilim2015failure]证明最优性。在本文中，我们演示了如何将CP模型优雅地集成到DP方法中作为子程序，以利用现有CP求解器中实现的强大全局约束传播。为此，当前DP状态、制造周期的上界和当前决策被作为约束施加到CP模型中。计算此传播的不动点会导致任务执行区间更紧和制造周期下界更强，最终减少DP方法中的转移次数。此外，CP可用作代理模型，通过基于每个状态可行性检查的二分搜索来进一步收紧下界。这种混合DP-CP框架自然地建模了PSSP，并通过放松优先级子集促进了大规模邻域搜索（LNS）方案。在标准基准上的实证评估证实了这种混合的可行性，表明我们的方法有效地利用了CP全局约束，并且在探索节点数量方面与标准纯CP方法具有竞争力。我们的贡献总结如下：

- •为了改善任意时间性能，我们将[GromichoHST12]中提出的基于层的DP搜索替换为*任意时间列搜索*（ACS）[vadlamudi2012anytime]。
- •我们提出了一种DP和CP模型的混合，其中全局约束NoOverlap的力量发挥着核心作用。
- •新框架原生处理PSSP，并展示了其在大规模邻域搜索中改进解的能力。
- •在著名基准套件上进行了实证评估。

本文的其余部分组织如下。第2节回顾相关工作。第3节介绍本文使用的基本概念。第4节描述最先进的DP模型，而第5节介绍我们对基于层DP的任意时间列搜索的改编。第6节详细介绍了针对PSSP的混合DP-CP框架。大规模邻域搜索（LNS）在第7节中描述。第8节对所提出的方法进行了全面的实证评估。最后，第9节总结全文。

## 2 相关工作

一项密切相关的工作由Marijnissen等人[marijnissen2026domain]并行且独立地开发，也提出了一个通用框架，用于将CP传播集成到领域无关动态规划（DIDP）[kuroiwa2023domain]中。他们的工作评估了DP和CP在诸如带时间窗的单机调度、RCPSP和TSPTW等问题上的协同作用，主要使用A\*和完全任意时间波束搜索（CABS）。[marijnissen2026domain]的DIDP框架旨在跨问题类实现领域无关性和通用性。它将CP视为一个黑盒，用于可行性检查和对偶界计算，但不利用CP的域过滤能力。我们的集成更具问题特异性，并特意针对部分车间调度问题（PSSP）的结构进行了定制。我们以更深度耦合的方式利用CP传播：NoOverlap全局约束的不动点用于在每个DP转移中*发现新的优先级约束*，并且这些优先级被显式地纳入DP状态本身。一个更细微的差异是我们采用任意时间列搜索（ACS）作为主要搜索策略，而[marijnissen2026domain]专注于A\*和CABS。

## 3 部分车间调度问题（PSSP）

我们考虑*部分车间调度问题*（PSSP），其定义为一组有限的操作O=\{o1,...,oN\}，需在一组有限的机器M=\{M1,...,Mm\}上执行，且|M|=m。这组操作被划分为n=N/m个子集，使得每台机器在每个划分中恰好分配给一个操作。每个操作o∈O有一个指定的处理时间po>0，需要一台特定的机器m(o)∈M独占使用且不可抢占，并且与一个特定的划分j(o)相关联。此外，操作受一组优先级约束，由有向无环图（DAG）G=(O,E)表示。边(o,o′)∈E表示操作o必须在操作o′开始前完成，记为o⋖o′。操作o的后继集合记为succs(o)，前驱集合记为preds(o)。该问题的一个解是为每个操作o∈O分配一个开始时间ψo，使得所有优先级约束（对所有(o,o′)∈E有ψo′ ≥ ψo+po）以及机器和划分的析取约束（同一台机器/划分上的两个操作在时间上不重叠）都得到满足。目标是最小化制造周期Cmax=max_{o∈O}(ψo+po)。这个通用的PSSP公式概括了经典问题，如作业车间调度问题（JSP）和开放车间调度问题（OSP）。在经典的JSP中，操作集被划分为称为作业的不相交子集，优先级图E由一组不相交的有向路径组成，每条路径对应一个作业。在OSP中，操作之间没有初始优先级约束（E=∅），但属于同一作业的操作在时间上不能重叠，需要额外的析取约束。对于表2中显示的三个作业三台机器的JSP实例，优先级E等于{(o1,o2), (o2,o3), (o4,o5), (o5,o6), (o7,o8), (o8,o9)}。作业1由{o1,o2,o3}定义，作业2由{o4,o5,o6}定义，作业3由{o7,o8,o9}定义。表2给出了表2中JSP实例的一个解。

表1：一个3作业3机器的JSP实例。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 |   |   |   |   |   |   |   |   |   |   |   |
| M2 |   |   |   |   |   |   |   |   |   |   |   |
| M3 |   |   |   |   |   |   |   |   |   |   |   |

o4 | o1 | o9 | o7 | o2 | o6 | o5 | o8 | o3
Job 1 | Job 2 | Job 3

表2：表2实例的解。

## 4 动态规划方法

JSP的DP公式最初由Gromicho等人[GromichoHST12]提出，随后由Hoorn等人[HoornNOG17]改进，并被Ozolins[Ozolins20]重用。在这种方法中，操作通过固定其开始时间来调度。只有当操作在优先级图中的所有前驱都已被调度时，该操作才变得可调度。然后该操作在其最早可能开始时间被调度，确保在其所需机器上没有时间重叠。搜索空间中的一个节点代表一个DP状态，由剩余未调度操作的最早可能开始时间定义。由于不同的调度决策序列可能导致完全相同的状态，搜索空间形成一个图而非简单的树。两个节点之间的转移成本对应于部分解制造周期的增量增加。Hoorn等人[HoornNOG17]逐层探索这个状态图，其中图上的最短路径产生最优制造周期的调度。形式上，DP状态是一个三元组S=⟨ψ,Λ,done⟩，其中：

- •ψ跟踪每个操作的最早可能开始时间。
- •Λ记录最后调度操作所在的机器ID。
- •done表示已经调度的操作集。

状态S定义了一个部分序列T_S，其当前制造周期记为Cmax(S)。根据我们的可调度规则，当前可用操作集数学上定义为：
ε(S) = {o ∈ O \ done(S) | preds(o) ⊆ done(S)}

为了缓解搜索空间的指数级增长，作者引入了优势规则。这些规则允许算法安全地丢弃被支配的转移和节点，同时在数学上保证至少一条通向最优解的路径被保留。

### 4.1 转移优势

给定一个完整解和一个开始时间分配，该解可以通过从ε(S)中依次选择一个操作并尽可能早地调度（不违反机器约束）来获得，直到所有任务都被调度。由于在给定阶段可能有多个任务可调度，不同的任务选择顺序可能产生相同的解。为了防止这种冗余，应用了*转移优势*规则，确保任何特定解仅由单个任务序列生成。形式上，我们定义η(S)为合法允许扩展T_S的可用操作子集。一个操作只有在严格延长制造周期或使用Λ打破平局时才有资格进入η(S)：

###### 定义4.1。一个操作o ∈ ε(S)属于η(S)如果满足以下条件之一：
- •ψo+po > Cmax(S)
- •ψo+po = Cmax(S) ∧ m(o) > Λ(S)

###### 示例4.2。图2和图2说明了定义4.1的两种情况。