英语原文共 12 页

准时制车间作业调度的拉格朗日约束问题

菲利普·巴普蒂斯特法①，马尔塔·弗拉米尼②，弗兰西斯·索尔德③

1. 法国帕莱索理工学院CNRS LIX实验室
2. 意大利罗马大学自动化信息中心
3. 法国巴黎CNRS LIP6实验室

摘要

我们研究了具有提前/延迟惩罚的车间作业调度问题。我们描述了该问题的两种拉格朗日松弛法。第一种是基于优先约束的松弛法，第二种是基于机器约束的松弛法。我们引入专用的算法来解决相应的对偶问题。第二个问题是用一种简单的动态规划算法求解的，而第一个问题则需要通过分支定界法来求解NP-hard问题。在这两种情况下，我们通过松弛法可以得到下界以及启发式的解。最后，我们介绍了一种简单的局部搜索算法，以改进所找到的最优解，并报告了计算结果。

关键词：车间作业调度问题，提前/延迟问题，拉格朗日松弛法

1 介绍

准时制库存管理在工业中的重要性促使了对理论调度模型的研究，该模型抓住了这一理念的主要特点。在这些模型中，许多研究都致力于提前/延期问题，在此类问题中，过早完成（这将导致需要库存）和延迟完成都是不利的。到目前为止，由于这些问题的难处理性，大部分工作都集中在单机问题上。本文研究了复杂作业车间环境下的提前/延期问题。

我们考虑一个作业车间调度问题，它由一组n个作业J ={J₁，hellip;，J_n}和一组m台机器M ={M₁，hellip;，M_m}组成。每个作业J_i是由n_i个有序操作组成的一条链，O_i,其中O^k_i是作业J_i的第k个操作。对于每项操作O^k_i，我们都有一个截止日期d_i^k和一个处理时间p_i^k。操作O^k_i必须由指定的机器M(O^k_i) isin;M来处理。同样，对于每台机器M_uisin;M，我们用upsilon;(M_u)来表示必须由机器M_u来处理的一组操作。

我们的目标是计算出一种可行的调度安排，即得出所有操作O^k_i的完成时间C_i^k。为了评估调度的成本，我们将E_i^k = max(0,d_i^k－C_i^k)和T_i^k = max(0, C_i^k－d_i^k)定义为操作O^k_i的提前和延迟时间。如果E_i^k gt;0 (或T_i^kgt;0)，则操作O^k_i提前完成(或延迟完成)。

对于每项操作O^k_i，我们有两个惩罚其提前或延迟完成的惩罚系数alpha;_i^k和beta;_i^k。因此，考虑到提前的操作是由成本alpha;_i^kE_i^k惩罚的，而延迟的操作是由成本beta;_i^kT_i^k惩罚的，我们定义了一个成本函数。其目标是使所有操作的提前和延迟成本之和最小化：

.

问题的约束条件如下：

• 对于{1，hellip;，n}中的任意i，第一个操作在时间0之后开始，

• 优先约束:对于同一作业的每对连续操作O^k_i和O_i^{k 1}，在完成操作O^k_i之前，无法进行操作O_i^{k 1}，即对于i = 1，hellip;，n和k = 1,hellip;，n_i－1:

.

• 资源约束(也称为析取约束):对于每台机器M_uisin;M,两个不同作业的两个操作O^k_i和O^h_j，在集合upsilon;(M_u)中，不能同时处理，即对于i,j=1,hellip;，n ,ine;j，且对于 k = 1，hellip;，ni和h = 1，hellip;，n_j：

或.

贝克和雷法洛[1]调查了这个问题的一个特例，在这个特例中，除了每个作业的最后一个操作之外，所有操作都没有提前和延迟惩罚成本。他们的方法是基于约束规划和线性规划的混合使用的。线性规划模型用于计算部分序列操作的最佳启动时间，而约束规划有助于修正析取约束。丹娜、佩伦[2]以及丹娜等人[3]提出了另一种利用整数线性规划和局部搜索的混合方法，并已证明该方法可以找到更好的调度方法。然而，该模型的一个缺点是，它导致了每个作业J_i的前n_i－1个操作被尽可能早地处理，从而引发了作业的后两项操作之间的等待时间(和存储成本)，而这与准时生产的理念相矛盾。在我们的模型中，通过考虑d_i = d_iⁿⁱ是J_i的截止日期和任何操作O^k_i的截止日期是d_i^k= d_i-sum;_j＞kP_i^j，解决了这一问题。因此，在每项操作按其截止日期完成的理想情况下，作业是准时的，且操作之间没有等待时间。

一些研究人员已经将拉格朗日松弛法应用于作业车间问题或诸如资源受限的项目调度问题等更复杂的问题[4]。简而言之，人们已经研究了两类松弛。

• 一类方法是从时间索引公式开始计算的，可以放松机器约束。然后将所要解决的子问题简化为使用任意成本函数对受优先约束的操作进行调度的问题。根据初始调度约束，作者运用了各种技术来解决该问题。或是在优先约束的结构是一条链或树时使用动态规划[5]，或是在一般情况下运用切割计算[6]，又或是使用单纯形算法[7]。
• 陈和卢[8]放松了优先级约束以及将操作完成时间与总成本联系起来的约束。当所有的这些约束条件都放松后，要解决的子问题被分解成了一组多项式的可解问题。卡斯卡维里斯和卡拉马尼斯[9]使用了类似的方法来解决带有存储成本和二次延迟惩罚的车间作业问题。

在本文中，我们分别基于优先约束的松弛和资源约束的松弛来评估了这两种松弛技术的效率。根据最近针对单机提前/延迟调度问题的分支定界算法的改进[10]，我们研究出了前一种松弛算法。据我们所知，将这种方法运用在这类问题的下界设置中是很新颖的。这个下界的另一个有趣之处在于它比陈和卢[8]的松弛约束性更强，这是因为在我们的方法中，资源约束毫不松弛，也就是说，我们对优先约束有一个纯松弛。

在第2节中介绍了这个下限，第3节介绍了按照[5]中描述的方法放松资源约束的方法。4.1节研究了这些下界的有效性:首先给出了计算上界的启发式方法，然后将两个下界与ILOG CPLEX提供的下界和上界进行了实验比较。

2 放松优先约束

在本节中，我们是基于该问题的基本公式的。这些公式是直接从该问题的方程式(1)-(4)的定义推导而来。为了加强下列松弛条件，我们为每项操作O^k_i定义了发布日期r_i^k=sum;_1le;hle;k-1P_i^h。接着,我们可以得到：

我们将操作O^k_i和O_i^{k 1}间的优先约束与一个拉格朗日乘子lambda;_i^kge;0联系起来。下文中，C和lambda;分别表示完成时间向量和拉格朗日乘数向量。拉格朗日函数L（C, lambda;）的定义如下:

根据lambda;_i⁰=lambda;_iⁿⁱ=0的假设，我们可以将（5）写为更简洁的形式：

（6）

其中，

对于给定的向量值lambda;，我们搜索在其余约束条件下的给定C值的L(lambda;)的最小值，即L(lambda;,C)的最小值。

该问题可分解为m个独立的具有提前和延迟惩罚成本的单机调度子问题，即当确定时，。

不难看出，P_u(lambda;)是一个具有提前/延迟惩罚的单机调度问题。这个问题在很大程度上是NP-hard问题，但是可以通过由索尔德和克达·西德胡姆提出的高级分支定界算法[10]来有效地解决。然后我们通过运用一个标准的次梯度算法找到使函数L（lambda;）取得最大值的向量lambda;^lowast;。在每次迭代中,当rho;isin;R 且▽是一个次梯度时，我们通过添加rho;nabla;来修正拉格朗日乘数向量。首先，rho;= 1，且所有乘数均为0。然后，当目标函数的值在连续10次迭代后仍未得到改善时，将rho;乘以0.7。当参数rho;小于10^minus;3时，算法停止。

由于分支定界法十分耗时，我们采用以下启发式算法来加快收敛速度。在收敛的初始步骤中，我们使用基本的启发式算法[11]来计算单机问题的上界(因此，在这些步骤中我们没有有效的下界)。该方法仅能用于收敛于一个“良好的”lambda;。一旦这个初始收敛阶段完成，我们就转向分支定界法。

我们没有使用次梯度法，而是尝试使用肖尔算法[12]中的Solvopt算法实现。但由于拉格朗日子问题求解时间较长，我们无法完成收敛过程，且得到的解并不优于基本次梯度算法得到的解。

从理论的角度来看，我们注意到,陈和卢[8]的松弛法受到了了L(lambda;^lowast;)的严格控制。我们只放松了优先约束,而他们还放松了约束E_i^k = max(0,d_i^k－C_i^k)和T_i^k = max(0, C_i^k－d_i^k)。

3 放松资源约束

在本节中，基于该问题[13]的时间索引公式，我们考虑了资源约束的拉格朗日松弛。我们引入了一个时间域T，它可以计算如下:

我们还引入了二进制{0,1}变量的集合，其中泛型变量x^t_ik是指第t时刻的操作O^k_i。每个变量x^t_ik的定义如下:

x^t_ik=

考虑到这组新变量，我们可以计算提前和延迟成本如下:

现在考虑资源约束。对于每台机器M_uisin;M和每一个即时时刻tisin;[0, T], upsilon;(M_u)中的两项操作不能重叠,也就是说,

因此,对于给定的一个时间t时刻isin;[0,T]和一台机器uisin;M，上述约束意味着如果一项操作O^k_iisin;upsilon;(Mu)在t时刻前开始,且在t时刻尚未完成,则至少在t时刻前的tminus;P^k_i 1时间内, upsilon;(Mu)内的其他操作不可以开始。综上所述，该初始问题可以表述为：

我们将拉格朗日乘数子lambda;_utge;0与每个资源约束关联起来。则提前和延误可表示为：

拉格朗日函数L（lambda;）正是：

其中w^t_ik和K是lambda;的简单函数

且

我们很容易看出，当L_i（lambda;）为下列形式时，L（lambda;）可被分解为

解决包含调度作业J_i的O¹_ihellip;Oⁿⁱ_i作业集的单个子问题，只需考虑其中的优先约束，从而最小化任意目标函数。

资料编号：[4663]