带时间窗口的单工件排序问题

The Scheduling Problem of Single Job with Time Windows

摘要: 排序是为加工若干个工件或者完成若干项任务而对资源按时间进行高效率的分配，本文讨论一个工件的情况下对多台机器进行排序，从而使加工时间最短的问题。在这个问题中给定一个时间窗口作为约束，机器只能在规定的时间窗口内运行。分析该问题是NP-难问题，并给出一个近似算法，讨论该近似算法的近似比不超过3/2，该近似算法的时间复杂度为O(m²)。

Abstract: Scheduling is the efficient allocation of resources according to time in order to process a number of jobs or complete a number of tasks. This paper discusses the problem of scheduling multiple machines in the case of one job so as to minimize the processing time. In this problem, we give a time window as a constraint; machines can only run within the time window. The problem is NP-hard and an approximate algorithm is given. The approximate ratio of the approximate algorithm is not more than 3/2. The time complexity of this algorithm is O(m²).

1. 引言

排序是为加工若干个工件或者完成若干项任务而对资源按时间进行高效率的分配，工厂在加工的时候，为了在盈利的同时令供应商、客户都满意，在保证按时交付产品的同时也要考虑到自己的成本问题，怎样让成本最小、花费时间最少、运输成本最小都是排序理论所要研究的问题。近年来国内外学者在排序领域取得了众多的研究成果。刘洋 [1] 分析了有新任务到达的包含时间窗口的多资源动态调度问题中的主要约束类型，建立了调度模型，提出了模型的启发式迭代修改求解方法。Chung-Yee Lee [2] 讨论了机器释放时间不同的几种情况下的理论结果，大多数问题是NP-难的，作者给出了伪多项式时间算法加以解决。Vickson [3] 研究了最大延误排序问题 $1\left|\right|T_{\max }$ 加工时间可控的费用最小问题。O. Braun [4] 等人将带时间窗口的单机排序问题添加了时间限制的约束条件，证明了当约束条件 $B\ge 2$ 时该问题是NP-难的，An Zhang [5] 等人给出了这个问题的多项式时间算法。Mostafa Khatami [6] 等人运用启发式算法和ILS算法更为有效率地解决了m台机器的有序流水线问题。

本文主要考虑一个工件在多台机器上加工的机器排序问题，与前述问题不同的是，本文在每天添加时间窗口作为机器运行时间的约束条件，要求所有机器都只能在时间窗口所规定的时间内运行。工厂在对工件进行加工时，机器运行的时间越长，成本就越高，所以要对机器进行排序，使得机器工作的天数最小，从而减少生产成本。本文给出了一个该问题的近似算法，并进行近似度分析，为工件的加工排序提供方案。

2. 问题简介

设有一个工件要在m台机器上进行加工，工件在每台机器上的加工时间为 $t_1,t_2,\cdots ,t_m$，有时间窗口 $\left[\alpha ,\beta \right]$，记 $t=\beta -\alpha$，( $\alpha <\beta$ 且 $\alpha ,\beta \in \left[0,24\right]$ )。其中 $\alpha$ 表示机器开始运行的时间， $\beta$ 表示机器结束运行的时间。所有机器的工作周期以天为单位，每天只能在时间窗口所规定的时间内运行，每台机器的工作时间不可中断，工件在同一时刻只能在一台机器上加工，机器之间没有顺序，要求对机器进行排序，使工作天数最小，设工作天数为k。

求 $\text{min}k$。

数学描述：

记 $x_{ij}=\{\begin{array}{l}1若第j台机器在第i天工作\\ 0若第j台机器不在第i天工作\end{array}$ $i=1,\cdots ,k;j=1,\cdots ,m$。

约束条件为 ${\displaystyle \underset{j=1}{\overset{m}{\sum }}{x}_{ij}{t}_j}\le t\left(i=1,\cdots ,k\right)$。

${\displaystyle \underset{\text{i}=1}{\overset{k}{\sum }}{x}_{ij}}=1\left(j=1,\cdots ,m\right)$。

也即

① $\{\begin{array}{l}{x}_{11}{t}_1+x_{12}{t}_2+\cdots +x_{1m}{t}_m\le t\\ x_{21}{t}_1+x_{22}{t}_2+\cdots +x_{2m}{t}_m\le t\\ ⋮\\ x_{k1}{t}_1+x_{k2}{t}_2+\cdots +x_{km}{t}_m\le t\end{array}$

② $\{\begin{array}{l}{x}_{11}+x_{21}+\cdots +x_{k1}=1\\ x_{12}+x_{22}+\cdots +x_{k2}=1\\ ⋮\\ x_{1m}+x_{2m}+\cdots +x_{km}=1\end{array}$

只需考虑 $k\le m$ 的情况。

记 $A=\left(\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1m}\\ x_{21}& x_{22}& \cdots & x_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ x_{k1}& x_{k2}& \cdots & x_{km}\end{array}\right)$。其中A的每一列只有一个元素为1，其余均为0，且 $k=r\left(A\right)$。

目标函数：求mink。

3. 对该问题的NP性讨论

定理1 上述问题是NP-难的。

证明：问题I：给定m个物品和一些容量为t的背包，m个物品的大小分别为 $\left\{t_1,t_2,\cdots ,t_m\right\}$，需要把每个物品分别放入背包中，物品的大小不能超过背包的容量，每个物品不可分割。问是否存在可以装下所有物品的最小背包数k。

问题II：设有一个工件，m台机器，工件在每台机器的工作时间记为 $t_1,t_2,\cdots ,t_m$，有时间窗口 $\left[\alpha ,\beta \right]$，记 $t=\beta -\alpha$，( $\alpha <\beta$ 且 $\alpha ,\beta \in \left[0,24\right]$ )。其中 $\alpha$ 表示机器开始运行的时间， $\beta$ 表示机器结束运行的时间。所有机器每天只能在时间窗口内运行，每台机器的工作时间不可中断，工件在同一时刻只能在一台机器上加工，要求对机器进行排序，使工作天数最小，设工作天数为k。

若I有一个可行解k，

记 $x_{ij}=\{\begin{array}{l}1若将第j个物品放在第i个背包里\\ 0若不将第j个物品放在第i个背包里\end{array}$ $i=1,\cdots ,k;j=1,\cdots ,m$。

记 $A=\left(\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1m}\\ x_{21}& x_{22}& \cdots & x_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ x_{k1}& x_{k2}& \cdots & x_{km}\end{array}\right)$，记 $T=\left(\begin{array}{c}{t}_1\\ t_2\\ ⋮\\ t_m\end{array}\right)$， $C=\left(\begin{array}{c}t\\ t\\ ⋮\\ t\end{array}\right)$，则由问题I可以得到 $AT\le C$，而k是满足该条件的最小背包数。在问题II里 $t_1,t_2,\cdots ,t_m$ 表示每台机器的工作时间，t表示每天的最长工作时间，当问题

II满足了 $AT\le C$ 之后，可直接得到k就是要求的最小工作天数。所以问题I可以多项式规约为问题II。已知问题Ⅰ是NP-难的 [7] [8]，所以问题II也是NP-难的。

4. 算法设计

Input: $x_{ij}\left(i=1,\cdots ,m;j=1,\cdots ,m\right);t_i\left(i=1,\cdots ,m\right)$。

Output: k的值。

Step1：先将m台机器按加工时间从大到小排列，不妨设为 $t_1\ge t_2\ge \cdots \ge t_m$。加工时长大于 $t/2$ 的机器记作大机器，设有 $k^{\prime }$ 台大机器，所需加工时间分别是 $t_1,\cdots ,t_{k^{\prime }}$。

Step2：按照每天运作一台大机器的方式先对大机器进行排序，即令

$x_{ij}=\{\begin{array}{l}1\left(i=j=1,\cdots ,k^{\prime }\right)\\ 0\left(j\ne i且i=1,\cdots ,m;j=1,\cdots ,k^{\prime }\right)\end{array}$

Step3：令 ${t^{\prime }}_1=t_1$， ${t^{\prime }}_2=t_2$， $\cdots$， ${t^{\prime }}_{k^{\prime }}=t_{k^{\prime }}$， ${t^{\prime }}_{k^{\prime }+1}={t^{\prime }}_{k^{\prime }+2}=\cdots ={t^{\prime }}_m=0$。

for ( $j=k^{\prime }+1,j<=m,j++$ )#外循环依次安排每一个小机器#

{ for( $i=1,i<=m,i++$ ) #内循环决定第j台小机器在哪一天运行#

if ( ${t^{\prime }}_i+t_j<=t$ )

$x_{ij}=1,x_{i+1,j}=0,x_{i+2,j}=0,\cdots ,x_{m,j}=0$

${t^{\prime }}_i={t^{\prime }}_i+x_{ij}{t}_j$ ；

break. #终止内循环，转入外循环#

else $x_{i,j}=0$ ；}

Step4:根据step3可以求出矩阵A，A的秩r(A)等于A中非零元的个数，且知 $k=r\left(A\right)$。

5. 算法分析

定理2 上述算法的近似比不超过3/2。

证明：已知上述算法所花费的总天数为k，大机器参与排序的天数为 $k^{\prime }$，记 $k^{″}=k-k^{\prime }$。将只对小机器进行排序的那些天记作小天，其余记作大天。显然小天共有 $k^{″}$ 天，大天共有 $k^{\prime }$ 天。在计算近似比时，将小天中的机器依次放在大天的空余部分，使大天的空余部分完全被占用，再依次将这些小天中的机器补在机器未被动用的小天的空余部分，使其空余部分完全被占用，将全部机器都被使用的小天数记作 $d_2$，机器未被动用的小天数加上机器未使用完的那一天记作 $d_1$，则 $k^{″}=d_1+d_2$.记最优解为OPT。则有

$k^{\prime }+d_1\le OPT$ (1)

$\frac{k^{\prime }t}{2}+\frac{d_{1}t}{2}\ge d_{2}t\Rightarrow \frac{1}{2}\left(k^{\prime }+d_1\right)\ge d_2$

$\frac{1}{2}\left(k^{\prime }+d_1\right)\ge d_2$ (2)

将(2)式代入(1)式中得

$OPT\ge k^{\prime }+d_1$

$\Rightarrow \frac{1}{2}OPT\ge \frac{1}{2}\left(k^{\prime }+d_1\right)$

$\Rightarrow \frac{1}{2}OPT\ge d_2$

所以

$OPT+\frac{1}{2}OPT\ge k^{\prime }+d_1+d_2$

$\frac{3}{2}OPT\ge k$

$\frac{k}{OPT}\le \frac{3}{2}$.

因此上述算法的近似比不超过3/2。

定理3 上述算法的时间复杂度为 $O\left(m^2\right)$。

证明：第一步的时间复杂度为 $O\left(m\log m\right)$，第二步的时间复杂度为 $O\left(m\right)$，第三步的时间复杂度为 $O\left(m^2\right)$，第四步的时间复杂度为 $O\left(m\right)$，所以该算法的时间复杂度为 $O\left(m^2\right)$。

6. 结论

关于带时间窗口的单工件在多台机器上的排序问题，本文给出了一个近似算法，并且证明了该近似算法的时间复杂度和近似比，而带时间窗口的多个工件在多台机器上的排序问题是这类问题未来的研究方向。

致谢

衷心感谢匿名审稿人对初稿提出的宝贵意见。