带有学习与恶化效应的机器受限的总完工时间问题

崔苗苗

（抚顺市四方高级中学，辽宁抚顺，112122）

带有学习与恶化效应的机器受限的总完工时间问题

崔苗苗

（抚顺市四方高级中学，辽宁抚顺，112122）

本文研究一种带有学习和恶化效应，并且机器具有可用性限制的单机排序问题。在这种模型中，工件的加工时间与所排位置及开始加工时间有关，以及机器在加工过程中，由于发生故障或进行维护与保养等原因产生的可用性限制。本文讨论的目标函数为极小化总完工时间的单机问题，对于机器在任意时间段维修的情况，分别给出了动态规划算法，分析了算法复杂性。

排序；学习效应；恶化效应；机器可用性限制；算法复杂性；动态规划

0 引言

本文考虑学习和恶化效应模型 pi[r]=（ai+bt）ra，并结合机器具有可用性限制的情况，研究极小化总完工时间的单机问题。问题描述如下：设有n 个工件J1,J2,…,Jn，工件Ji的基本加工时间为 ai，工件在t1前t时刻开始加工时，排在第r个位置的实际加工时间为 pi[r]=（ai+bt）ra，工件在t2后t时刻开始加工时，排在在t2后第k个位置的实际加工时间为 pi[k]=（ai+bt）ka，其中α≤0是学习因子，b＞0为工件的恶化率，工件加工过程中不允许中断。给定一个排序π，工件Ji的完工时间记为Ci。对于单机且机器在 [t1, t2] （t1＜t2）区间内不能加工工件的极小化总完工时间问题，用三参数表示法记为1nr−a, pir=(ai+bt) rα∑Ci；

1 单机问题

Adiri 等[12]证明了是NP-难的。显然，问题也是NP难的，并且对于学习与恶化效应模型的单机极小化总完工时间的排序问题有如下结论：

引理1[6]对于问题工件按ai非减排列（shortest processing time first, SPT rule）可以得到最优排序。

根据上面引理，对于学习和恶化效应的机器可用性限制的单机排序问题，可以得到下面的结论。

证明 用反证法。由于机器在[t1, t2]时间区间内不能加工工件，那么工件只能排在t1时刻前或t2时刻后。设某最优排序违反了按基本加工时间ai非减排列规则。

（i）首先证明排在t1前的工件是按基本加工时间非减排列（SPT规则）的。

不失一般性，不妨设在排序π中排在t 1前第r 和第r+1个位置的两相邻工件表示t1时刻前第ir个工件排在第r 个位置加工时的实际加工时间，C[r]表示它的完工时间，则第一个工件Ji1排在第一个位置加工的实际加工时间为：

（3）式说明交换后目标函数值比交换前小，这与π是最优排序矛盾。

（ii）下面证明排在t2后的工件也是按ai非减排列（SPT规则）的。

假设t2后第一个开始加工的工件为，其开始加工时间为，定义表示在π中第个工件排在后第l个位置加工时的实际加工时间，表示它的完工时间，则排在后第一个位置加工的加工时间为：

完工时间为：

于是，工件J1…Ji的总完工时间分以下两种情况：

由以上分析可得动态规划算法如下：

动态规划算法1（DP1）：

下面分析DP1的算法复杂性。

由式（4）可得t2后第l个工件的完工时间为：

则第l+1个工件的加工时间为

对于机器在零时刻进行维修的情况，可以有下面推论。

2 结语

现实生活中，人们总是希望机器在加工过程中，能够提高工件的加工效率，缩短加工时间，但事实上在提高工人加工效率的同时，也存在机器的恶化现象，并且机器在加工过程中会出现故障或进行维护与保养等现象，导致机器在某段时间内不能加工工件。因此，本文将学习和恶化现象与机器具有可用性限制结合起来，研究了极小化总完工时间的单机问题，并给出了动态规划求解算法，使得问题具有广泛的应用价值和实际意义。但对于具有其它学习和恶化效应的函数问题以及机器具有可用性限制的流水作业排序问题，还有待进一步研究。

[1]Wu Chin-Chia, Hsu Peng-Hsiang , Chen Juei-Chao et al. Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times[J]. Computers & Operations Research, 2011 ,38（7）: 1025–1034.

[2]Biskup D. Single machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999,115（1）: 173-178.

[3]Liu Jing, Sun Shijie, He Longmin. Some single machine scheduling problems with learning effect under consistent condition[J].运筹学学报，2003（7）：21-28.

Machine - constrained total completion time with learning and worsening effects

Cui MiaoMiao
（Sifang Senior High School of Fushun City, FuShun LiaoNing，112122）

This paper investigates a single machine scheduling problem with learning and worsening effects and machine availability constraints. In this model, the machining time of the workpiece is related to the position and starting time of machining, as well as the usability limitations of the machine during processing due to failure or maintenance and maintenance. The objective function discussed in this paper is a single machine problem which minimizes the total completion time. For the maintenance of the machine at any time, the dynamic programming algorithm is given and the complexity of the algorithm is analyzed.

ranking; learning effect; worsening effect; machine availability limitation; algorithm complexity; dynamic programming