具有共同窗口和可拒绝工件的排序问题

The scheduling problem with common due-window and job-rejection

摘要

研究了同时具有可拒绝工件和共同窗口的单机排序问题，其中共同窗口的起始和结束时间都是决策变量。若工件在共同窗口期内加工完成，将不会产生额外费用，反之，则会产生提前或延误费用。对于被拒绝的工件，会有相应的拒绝费用。目标是确定哪些工件被接受或拒绝、接受加工的工作集合中的加工次序以及共同窗口的起始和结束时间，从而使得排序费用和拒绝费用的加权和最小，其中权重是位置权重。经过理论分析和算法设计，证明该问题存在时间复杂性更低的最优求解算法。

Abstract

It was considered that a single-machine scheduling problem with job-rejection and common due-window，which the starting time and finishing time of the common due-window were decision variables.If the job was completed in the common due-window，no additional cost would be incurred，otherwise，advance or delay costs would be incurred.If the job was rejected，a corresponding rejection cost wonld be incurred.The goal was to find out which jobs were accepted and rejected， the sequence of accepted job set，the starting and finishing times of common due-window，so as to minimize the weighted sum of scheduling cost and rejection cost，which the weights were the position weights.Through theoretical analysis and algorithm design，it is proved that there is an optimal solution algorithm with lower time complexity.

关键词

排序 / 可拒绝工件 / 单机 / 共同窗口 / 指派问题

Key words

scheduling / job-rejection / single-machine / common due-window / assignment problem

在经典排序问题中，默认所有的工件都是必须要加工的，然而为了降低制造成本，获得更大利润，加工商在加工过程中常会作出策略性选择。具体而言，他们会根据工件的加工时间和预期利润进行评估，选择性地拒绝加工那些制造时间长且利润小的工件。比如某些特殊型号的螺丝或螺母，市场需求不高且制造过程相对繁琐，因此制造商选择拒绝加工这些工件，以避免不必要的成本投入，这就是具有拒绝工件的排序问题^［1-2］。在此基础上，Zou等^［3］对带有维修活动的拒绝工件排序问题进行了研究，证明了所研究的排序模型均为NP-难问题，构造了求解该问题的伪多项式时间算法。在流水车间环境中，Mor等^［4］考虑了带有拒绝工件与学习效应的排序问题。Chen等^［5］研究了带有拒绝工件的排序问题，证明了这些问题是NP-难问题，并提出有效求解的近似算法。在平行机环境下，Zhong等^［6］及毕春燕等^［7］在拒绝工件的基础上考虑了带有准备时间或到达时间的平行机排序问题。Toksari等^［8］考虑了带有拒绝工件和学习效应的单机排序问题，并将极小化最大完工时间、总完工时间及总完工时间差的绝对值与拒绝成本之和转化为一个整体的指派问题进行求解。Koulamas等^［9］研究了在共同工期情况下带有拒绝工件的单机排序问题，他们对总延误问题和总加权延误问题分别给出了两个问题的NP-难证明，并给出了一种改进的近似算法和启发式算法。刘晓霞等^［10］研究了带有到达时间且拒绝工件总个数受限的单机平行分批排序问题。Mor等^［11］研究了在共同工期和拒绝上限条件限制下单机排序问题，目标函数为总提前延误和总加权提前延误，证明了这些问题都是NP-难问题，并提出了伪多项式时间算法。国峰等^［12］研究了具有拒绝工件和学习效应的资源分配单机排序问题，在线性资源和凸资源约束下，他们证明了一类正则目标函数是多项式时间可解的。刘春来等^［13］研究同时具有退化工件和老化效应的单机可拒绝排序问题，即工件的实际加工时间是与其开工时间和所在位置有关的函数，证明所研究的问题是NP-难问题，并给出了解决问题的一个全多项式时间近似方案。

文献［14］研究了工件允许拒绝的单机共同窗口指派问题，目标函数为极小化工件的排序费用和拒绝费用的加权和，其中权重为位置权重。他们证明此问题可以在O(n^{\mathrm{4}})时间内解决，其中n为工件个数。本文在文献［14］的基础上，分析最优解的性质，将确定接受加工以及拒绝加工的集合转化为一个整体的指派问题，即可在O(n^{\mathrm{3}})的时间内由匈牙利算法求得最优解，此整体的指派问题较文献［14］有更低的时间复杂度（即降低一个数量级n），且通过文献［14］中的算例验证了本工作所得结果的优越性。

1 问题描述

假设给定的n个工件要在一台机器上按照一定的顺序进行加工，其中工件的集合为N=\{J_{\mathrm{1}},J_{\mathrm{2}},\cdots ,J_n\}，同时满足机器只能一次处理一个工件，且不允许抢占（即加工的工件不可以中断）。令p_k为工件J_k的基础加工时间，R表示接受加工的工件集合，\overline{R}表示拒绝加工（rejection）的工件集合，集合R中的工件个数为|R|=n_A，如果工件J_k拒绝加工，这时产生的惩罚费用为e_k。令[k]表示排在第k个位置，本文目标是确定集合R和\overline{R}，集合R中的加工顺序、公共窗口（conw）的开始时间和窗口长度使\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in R}{e}_k最小，其中：d^{\text{'}}和d^{″}为窗口的开始和结束时间；D={d^{\text{'}}}^{\text{'}}-d^{\text{'}}为窗口长度；L_{[k]}为工件J_{[k]}的提前-延误惩罚；\alpha为窗口开始时间的权重；\beta为窗口长度的权重；w_k表示与位置k相关的权重（即位置权重）；与工件J_k本身无关。

（1）

同文献［14］一样，此问题可记为

\mathrm{1}|\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{w}|\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in R}{e}_k（2）

2 主要成果

根据文献［14］，有如下引理：

引理1 对于\mathrm{1}|\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{w}|\alpha d\text{'}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in \overline{R}}{e}_k存在最优解，d\text{'}=C_{[h]}，其中h满足；d\text{'}\text{'}=C_{[l]}，其中l满足，其中\mathrm{1}\le h\le l\le n_A。

注：若h不满足，即\beta >{\displaystyle \sum _{k=\mathrm{1}}^h}{w}_kl=h=n或\beta \le {\displaystyle \sum _{k=\mathrm{1}}^{h-\mathrm{1}}}{w}_k。对于\beta >{\displaystyle \sum _{k=\mathrm{1}}^h}{w}_k>{\displaystyle \sum _{k=\mathrm{1}}^{\mathrm{1}}}{w}_k，此时h=\mathrm{1}；对于\beta \le {\displaystyle \sum _{k=\mathrm{1}}^{h-\mathrm{1}}}{w}_k，根据h\le n_A，则有\beta \le {\displaystyle \sum _{k=\mathrm{1}}^{h-\mathrm{1}}}{w}_k\le {\displaystyle \sum _{k=\mathrm{1}}^{n_A-\mathrm{1}}}{w}_k，此时h=n_A，对应的，l=h=n_A。

若l不满足，则有\beta >{\displaystyle \sum _{k=l}^{n_A}}{w}_k或\beta \le {\displaystyle \sum _{k=l+\mathrm{1}}^{n_A}}{w}_k。对于\beta >{\displaystyle \sum _{k=l}^{n_A}}{w}_k，有\beta >{\displaystyle \sum _{k=l}^{n_A}}{w}_k>{\displaystyle \sum _{k=n_A}^{n_A}}{w}_k，即l=n_A；对于\beta \le {\displaystyle \sum _{k=l+\mathrm{1}}^{n_A}}{w}_k，根据h\le l，则有\beta \le {\displaystyle \sum _{k=l+\mathrm{1}}^{n_A}}{w}_k\le {\displaystyle \sum _{k=h+\mathrm{1}}^{n_A}}{w}_k，此时l=h。

引理2 对于\mathrm{1}|\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{w}|\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in \overline{R}}{e}_k存在最优解，使Z=\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in \overline{R}}{e}_k表示为

Z={\displaystyle \sum _{k=\mathrm{1}}^{n_A}}{\theta }_k{p}_{[k]}+\sum _{k\in \overline{R}}{e}_k（3）

其中

{\theta }_k=\left\{\begin{array}{c}\alpha +{\displaystyle \sum _{j=\mathrm{1}}^{k-\mathrm{1}}}{w}_j,\hspace{1em}k=\mathrm{1,2},\cdots ,h\\ \beta ,\hspace{1em}k=h+\mathrm{1},h+\mathrm{2},\cdots ,l\\ {\displaystyle \sum _{j=k}^{n_A}}{w}_j,\hspace{1em}k=l+\mathrm{1},l+\mathrm{2},\cdots ,n_A\end{array}\right.（4）

引理3 对于\mathrm{1}|\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{w}|\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in \overline{R}}{e}_k，若接受加工的工件数为n_A，则此问题的最优加工顺序可以归结为如下指派问题：

\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\hspace{1em}{\displaystyle \sum _{k=\mathrm{1}}^n}{\displaystyle \sum _{r=\mathrm{1}}^n}{W}_{kr}{X}_{kr}\\ \mathrm{s}.\mathrm{t}.\hspace{1em}\hspace{1em}{\displaystyle \sum _{r=\mathrm{1}}^n}{X}_{kr}=\mathrm{1},\hspace{1em}k=\mathrm{1,2},\cdots ,n\\ \hspace{1em}\hspace{1em}\hspace{1em}{\displaystyle \sum _{k=\mathrm{1}}^n}{X}_{kr}=\mathrm{1},\hspace{1em}r=\mathrm{1,2},\cdots ,n\\ \hspace{1em}\hspace{1em}\hspace{1em}{X}_{kr}\in \left\{\mathrm{0,1}\right\},k=\mathrm{1,2},\cdots ,n;r=\mathrm{1,2},\cdots ,n\end{array}（5）

式中：X_{kr}=\mathrm{1}为工件J_k排在第r个位置上，否则X_{jr}=\mathrm{0}。

W_{kr}=\left\{\begin{array}{c}{\theta }_r{p}_k,k=\mathrm{1,2},\cdots ,n_A\\ e_k,k=n_A+\mathrm{1},n_{\mathrm{A}}+\mathrm{2},\cdots ,n\end{array}\right.（6）

文献［14］给出了时间复杂性为O(n^{\mathrm{4}})的最优算法，即对每一个n_A(n_A=\mathrm{1,2},\cdots ,n)，对应一个指派问题，即求解n个指派问题式（5）—（6）。以下给出复杂性更低的算法，即时间复杂性为O(n^{\mathrm{3}})。

令X_{ikj}(i=\mathrm{1,2};k,j=\mathrm{1,2},\cdots ,n)是一个0，1变量，如果工件J_k排在第j个位置，X_{ikj}=\mathrm{1}，否则X_{ikj}=\mathrm{0}。如果工件J_k接受加工，则i=1。如果工件J_k拒绝加工，则i=2，这时的惩罚费用为e_k。在此情况下，可将确定接受加工的集合问题转换为如下指派问题进行求解：

\begin{array}{l}(\mathrm{A}\mathrm{P})\hspace{1em}\mathrm{m}\mathrm{i}\mathrm{n}\hspace{1em}{\displaystyle \sum _{k=\mathrm{1}}^n}{\displaystyle \sum _{r=\mathrm{1}}^n}\left({\theta }_r{p}_k{X}_{\mathrm{1}kr}+e_k{X}_{\mathrm{2}kr}\right)\\ \mathrm{s}.\mathrm{t}.{\displaystyle \sum _{k=\mathrm{1}}^n}{X}_{ikr}\le \mathrm{1},i=\mathrm{1,2};r=\mathrm{1,2},\cdots ,n\\ {\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}}}{\displaystyle \sum _{r=\mathrm{1}}^n}{X}_{ikr}=\mathrm{1},k=\mathrm{1,2},\cdots ,n\\ X_{ikr}\in \{\mathrm{0,1}\},i=\mathrm{1,2};k,r=\mathrm{1,2},\cdots ,n\end{array}（7）

由指派问题AP，即式（7）可以确定要加工的工件集合R（这时集合\overline{R}也确定了），确定完工件集合R后，可以用HLP规则^［15］确定最优的工件加工顺序，即最大的{\theta }_k对应最小的p_k，第二大的{\theta }_k对应第二小的p_k，依次类推，这时，问题\mathrm{1}|\mathrm{r}\mathrm{e}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n},\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{w}|\alpha d^{\text{'}}+\beta D+\sum _{k\in R}{w}_k{L}_{[k]}+\sum _{k\in \overline{R}}{e}_k的时间复杂性为O(n^{\mathrm{3}})。

下面用文献［14］同样的例子说明此问题是如何求解的。

例1考虑n=\mathrm{6}、\alpha =\mathrm{10}、\beta =\mathrm{30}，其他数据见表1和表2所示。

解：现根据指派问题AP，即式（7）进行计算，此时n_A=n，则由引理1和式（4）得，h=\mathrm{3}、l=\mathrm{4}、{\theta }_{\mathrm{1}}=\mathrm{10}、{\theta }_{\mathrm{2}}=\mathrm{17}、{\theta }_{\mathrm{3}}=\mathrm{37}、{\theta }_{\mathrm{4}}=\mathrm{40}、{\theta }_{\mathrm{5}}=\mathrm{27}、{\theta }_{\mathrm{6}}=\mathrm{13}，指派问题AP的系数矩阵见表3所示。用Lingo18.0求解指派问题AP，得工件集合R的最优加工顺序为[J_{\mathrm{1}}]，拒绝工件为[J_{\mathrm{2}},J_{\mathrm{3}},J_{\mathrm{4}},J_{\mathrm{5}},J_{\mathrm{6}}]，根据此结果以及引理1可得h=l=\mathrm{1}，对应的最优目标函数值为1 096。用指派问题AP得出的结果同文献［14］的最优解一样，但计算量明显较少。

3 结论

本文研究了具有位置权重和可拒绝工件的窗口指派单机排序问题，在该问题中，所有工件被明确划分为接受工件集和拒绝工件集。对于接受工件集中的工件，它们共享一个交货期窗口，只有在窗口内完成才不产生额外费用；超出窗口则会受到提前或延误的惩罚。而对于拒绝工件集中的工件，则会因拒绝而产生相应的费用。证明存在一个复杂性更低的新算法，该算法在解决此类问题时，显著降低了时间复杂度。未来的研究可以考虑多处理机（包括流水作业和平行机）和拒绝工件相结合的问题，或者考虑其他更一般的目标函数问题。

参考文献

[1] Bartal Y， Lenonardi S， Marchetti S A， et al. Multiprocessor scheduling with rejection［J］. SIAM Journal of Discrete Mathematics， 2000， 13（1）： 64-78.

[2] Zhang L Q， Lu L F， Yuan J J.Single-machine scheduling under the job rejection constraint［J］.Theoretical Computer Science，2010，411（16/17/18）：1877-1882.

[3] Zou J， Yuan J J.Single-machine scheduling with maintenance activities and rejection［J］.Discrete Optimization，2020，38：100609.

[4] Mor B， Mosheiov G， Shapira D.Flowshop schedu-ling with learning effect and job rejection［J］.Journal of Scheduling，2020，23（6）：631-641.

[5] Chen R X， Li S S.Minimizing maximum delivery completion time for order scheduling with rejection［J］.Journal of Combinatorial Optimization，2020，40（4）：1044-1064.

[6] Zhong X L， Pan Z M， Jiang D K.Scheduling with release times and rejection on two parallel machines［J］.Journal of Combinatorial Optimization，2017，33（3）：934-944.

[7] 毕春燕， 万龙， 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法［J］. 运筹学学报， 2022， 26（2）： 73-82.

[8] Toksari M D， Atalay B.Some scheduling problems with job rejection and a learning effect［J］.The Computer Journal，2023，66（4）：866-872.

[9] Koulamas C， Steiner G.New results for scheduling to minimize tardiness on one machine with rejection and related problems［J］.Journal of Schedu-ling，2021，24（1）：27-34.

[10] 刘晓霞，余山杉，罗文昌.工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法［J］.运筹学学报，2020，24（1）：131-139.

[11] Mor B， Shapira D.Scheduling with regular performance measures and optional job rejection on a single machine［J］.Journal of the Operational Research Society，2020，71（8）：1315-1325.

[12] 国峰，王吉波.带有拒绝工件和学习效应的资源约束排序问题研究［J］.重庆师范大学学报（自然科学版），2021，38（1）：114-120.

[13] 刘春来，王建军.具有老化效应的单机共同工期安排和工件可拒绝排序问题［J］.运筹与管理，2021，30（7）：66-70，135.

[14] 徐景孝，吕丹阳，王吉波.带有拒绝工件的公共窗口指派单机排序问题［J］.沈阳航空航天大学学报，2022，39（2）：91-96.

[15] Hardy G H， Littlewood J E， Polya G.Inequalities［M］.Cambridge：Cambridge University Press，1967.

基金资助

辽宁省教育厅基础科研项目(JYTMS20230278)