具有学习效应且工件可拒绝单机排序问题探讨

余英　罗永超

摘要：文章对工件具有与已加工工件有关的安装时间且工件的加工时间具有学习效应的工件可拒绝的排序问题进行了研究；对目标函数为极小化最大完工时间与总拒绝费用之和以及极小化完工时间和与总拒绝费用之和分别给出了一个动态规划算法。

关键词：单机排序；学习效应；工件可拒绝；动态规划算法；目标函数 文献标识码：A

中图分类号：O223 文章编号：1009-2374（2015）29-0078-02 DOI：10.13535/j.cnki.11-4406/n.2015.29.039

具有学习效应的排序问题首先由Biskup提出，他假设工件的加工时间随着熟练程度的提高而越来越短，即工件越往后加工，所需的时间将减少。随后，Mosheiov和Sidney、Biskup和Simons、Koulamas和Kyparisis等进行了相关的研究。更多相关研究可参考文献[5]至参考文献[9]。

王吉波研究了工件的加工时间与已加工工件有关的学习效应的排序问题，并指出最小化最大完工时间、完工时间和以及完工时间平方和是多项式时间可求解的，而最小化加权完工时间和、最大延误在一定条件下是多项式时间可求解的。

工件可拒绝的排序模型首先由Y.Bartal等提出，他们分别研究了离线情形和在线情形下的的排序模型。S.S.Selden等探讨了极小化总拒绝费用和最大完工时间之和的可中断平行机模型。Y.He和X.Min研究了两台同类机以及三台同类机可拒绝的排序的一个特殊情形。D.Engels等证明了是NP-困难的，并给出了伪多项式时间的动态规划算法和FPTAS算法。S.Sengupta对目标函数为极小化总拒绝费用与最大延迟/延误的可拒绝排序模型进行了研究。

本文在参考文献[10]的模型的基础上，研究了工件可拒绝的排序问题，对原有理论进行了扩展。

1 问题假设

有一工件集需要在一台机器上加工，机器一次只能加工一个工件，且工件加工不可中断。工件排在第个位置加工的实际加工时间为，其中为工件的正常加工时间，为排在第个位置的工件的正常加工时间，，为常数。任一工件在加工前有一安装时间，第个位置的工件的安装时间为，且有，其中为常数，为排在第个位置工件的实际加工时间。以下将这类安装时间简记为。工件在加工过程中，由于有的工件加工时间非常长或费用很大，因此采取不加工此工件，而是通过支付一定的费用后送到外面去“外加工”或购买更合算。假设工件的拒绝费用为，表示加工工件的集合，表示拒绝工件的集合，所研究问题用参数法表示为：

2 的动态规划算法

引理：问题存在一个最优序，在该序中工件按的非降序排列。

证明：不妨假设工件序为，其中加工工件为，则：

，

所以的非降序为问题的一个最优序。

首先将工件按的非降序为工件编号。

用表示已加工工件数为个，且已排工件所对应的最优目标函数值，那么该动态规划算法的边界条件为：

现在考虑对于工件且加工工件个数为的任意最优排序。对于工件，此时有两种选择，即拒绝加工或者加工。

当加工工件时，，其中表示已加工工件中排在第个位置的工件的正常加工时间，表示已加工工件中排在第个位置的工件的实际加工时间。

当拒绝加工时，。

综合以上两种情况有：

该问题的最优值为。

在这个动态规划算法中，我们需要计算个的值，其中计算每个值需要的时间，所以这个动态规划算法的计算复杂性为。

3 的动态规划算法

引理：问题存在一个最优序，在该序中工件按的非降序排列。

证明：不妨假设工件序为，其中加工工件为，则：

可知的非降序为问题的一个最优序。

首先将工件按的非降序为工件编号。

用表示已加工工件数为个，且已排工件所对应的最优目标函数值，那么该动态规划算法的边界条件为：

现在考虑对于工件且加工工件个数为的任意最优排序，对于工件，此时有两种选择，即拒绝加工或者加工。

当加工工件时，，其中表示已加工工件中排在第个位置的工件的实际加工时间。

当拒绝加工时，。

综合以上两种情况有：

该问题的最优值为。

在这个动态规划算法中，我们需要计算个的值，其中计算每个值需要的时间，所以这个动态规划算法的计算复杂性为。

4 结语

本文对可拒绝加工的一类排序问题进行了研究，其中工件的加工时间具有学习效应，安装时间与已加工工件有关，对两类目标函数分别给出了动态规划算法。读者可以继续研究多机环境下相关的问题。

参考文献

[1] Bisup D.Single machine scheduling with learning considerationgs[J].European Journal of Operational Research，1999，115（1）.

[2] Mosheiov G.Sidney J B.Scheduling with general job-dependent learning curve[J].European Journal of Operational Research，2003，147（3）.

[3] Bisup D，Simons D.Common due date scheduling with autonomous and induced learning[J].European Journal of Operational Research，2004，159（3）.

[4] Koulamas C，Kyparisis G J.Single-machine and two-machine flowshop scheduling with general learning functions[J].European Journal of Operational Research，2007，178（2）.

[5] Kuo W H，Yang D L.Single machine scheduling with past sequence-dependent setup times and learning effects

[J].Information Processing Letters，2007，102.

[6] Jiang Z Y，Chen F F，Kang H Y.Single-machine scheduling problem with actual time-dependent and job-dependent learning effect[J].European Journal of Operational Research，2013，227.

[7] Kuo W H，Yang D L.Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect[J].European Journal of Operational Research，2006，（174）.

[8] Li S.Single-machine scheduling problem with deteriorating jobs and learning effects[J].Computer and Indusrial engineering，2009，57.

[9] 程明宝.工件具有指数学习效应的流水作业排序问题[J].暨南大学学报（自然科学版），2008，29（1）.

[10] Wang J B.Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect[J].Computers and Industrial Engineering，2008，55.

[11] Y.Bartal，S.Leonardi，A.Marchctti-Spaccamela，

J.Sgall and L.Stougie.Multiprocessor scheduling with rejection[J].SIAM Journal of Discrete Maths，2000，（13）.

[12] S.S.Seiden.Preemptive multiprocessor scheduling with rejection[J].Theoretical Computer Science，2001，2621.

[13] Y.He and x.Min.On-line uniform machine scheduling with rejection[J].Computin，2000，65.

基金项目：1.贵州凯里学院院级科研课题重点课题：基于非恒定加工时间的若干排序问题的研究（Z1402）；2.贵州省科学技术基金项目：基于共同交货期的提前延误排序问题（黔科合LH字[2014]7232）；3.凯里学院2014年重点学科（数学）（KZD2014004）。

作者简介：余英（1981-），女，浙江桐庐人，凯里学院数学科学学院教师，副教授，硕士，研究方向：排序理论和组合最优化。

（责任编辑：秦逊玉）