具有非线性安装时间和送出时间的单机排序问题

Single-Machine Scheduling Problems with Non-Linear Past-Sequence-Dependent Setup Times and Delivery Times

摘要: 本文讨论了同时带有非线性安装时间和送出时间的单机排序问题。工件的实际加工时间为与其开始时间和位置有关的函数。工件的安装时间和送出时间均与工件的加工位置有关，还依赖于已加工完成工件的实际加工时间，即p-s-d形式。研究了关于最大完工时间、总完工时间、加权完工时间、总完工时间 次方之和以及最大延误时间的目标函数。分别给出上述问题的最优排序规则。

Abstract: This paper studies the single machine scheduling problems with both non-linear setup times and delivery times where the actual processing time of a job is given as a function of its starting times and position in a sequence. The setup time and delivery time of a job are proportional to the jobs already processed and its scheduled position, that is, past-sequence-dependent (p-s-d). We consider the objective functions about the makespan, the total completion times, the total weighted completion times, the sum of the -th power of job completion times and the maximum tardiness. We give the optimal scheduling rules of the above problem respectively.

1. 引言

在传统的排序模型中，考虑加工工件具有安装时间的问题是非常必要的，Allahverdi和Aldowaisan [1] 提出带有安装情况的排序问题。常见的安装时间有两种：一种是各工件带有独立的安装时间，与加工顺序及已加工完的工件无关；另一种是安装时间依赖于工件的加工位置以及工件的实际加工时间。Kowamas和Kyparisis [2] 首次提出了安装时间与顺序有关的(即p-s-d)排序问题，并证明了一些问题的多项式可解性。同时也将结论扩展到非线性安装时间问题上。Yeh等 [3] 研究了带有非线性安装时间和学习效应的单机排序问题。目标函数是极小化总完工时间和加权总完工时间。

在实践过程中，许多工件的加工时间都会因诸多因素而减小，这就是所熟知的学习效应。Biskup [4] 首先提出加工工件具有学习效应的排序问题。Kuo和Yang [5] 研究了单机带有学习效应和p-s-d安装时间的排序问题，并证明了最大完工时间、总完工时间和总延误时间等问题的多项式可解性。Wang [6] 研究了单机带有p-s-d安装时间和学习效应依赖于已完成工件的加工时间的排序问题。目标函数是极小化最大完工时间、总完工时间等问题。Wang [7] 研究了单机带有p-s-d安装时间、学习效应和恶化效应的排序问题，分别证明了最大完工时间、总完工时间等问题在多项式时间可解。文献 [8] [9] [10] [11] 给出了其他关于具有学习效应和恶化效应的研究工作。

近年来，有关送出时间的问题也是备受关注。Koulamas和Kyparisis [12] 研究了带有p-s-d送出时间的单机排序问题，目标函数是极小化最大完工时间、总完工时间、最大延误时间和延误工件数。Yang和Yang [13] 研究了带有p-s-d送出时间和加工时间与位置有关的单机排序问题。目标函数是极小化总提前时间、总延误时间以及极小化与窗口的开始时间、窗口的大小、提前时间和延误时间有关的费用函数，以及极小化TADC和TADW问题。

本文研究同时具有学习效应和恶化效应的单机排序问题，将其与非线性安装时间送出时间相结合。分别研究有关于极小化最大完工时间、总完工时间、加权完工时间、总完工时间次方之和以及最大延误时间的目标函数。

2. 问题描述

研究单机问题，n个工件均无优先加工权，并且在0时刻均可加工。所有工件不允许中断并且不能同时加工。工件的加工时间为，其开始时间为t。若排在第r个位置，那么工件的实际加工时间可以表示为：

(1)

其中：代表工件的恶化率；是一个常量学习效应。

在文献 [3] 中，工件在排序中排在第个位置的安装时间为：

(2)

其中：为常数；代表排在第个位置工件的实际加工时间。

在文献 [13] 中，工件在排序中排在第个位置的送出时间为：

(3)

其中：为常数；代表排在第个位置工件的实际加工时间。

，，，，，，分别表示工件的完工时间；最大完工时间；总完工时间；总完工时间次方之和；加权完工时间；最大延误时间和工件的工期。用三参数表示法，本文研究的问题可表示为：

引理1：如果工件在时开始加工，则：

(4)

证明过程同Wang [7] ，此处不做过多赘述。

引理2：给定排序，问题

工件的完工时间为：

(5)

证明：由等式(1)~(4)，有

3. 主要结论

定理1：对于问题将工件按照恶化率非减的顺序排列(即：SDR原则)可得到最优排序。

证明：假设存在最优排序，其中工件和分别在两个相邻的位置，和是部分排序并且可能为空。假定中有个工件，因此工件和分别在第和个位置上，并且假定。而排序。分别计算、与、：

(6)

(7)

同理可得：

(8)

(9)

由(7)和(8)可得：

因为且。所以。即：。

同理可证。

因此，将工件按照恶化率非减的顺序排列(即：SDR原则)可得到最优排序。

定理2：对于问题将工件按照恶化率非减的顺序排列(即：SDR原则)可得到最优排序。

证明：在定理1的证明中，因为得出：

以及

因此：当时，有，证毕。

定理3：对于问题，将工件按照恶化率非减的顺序排列(即：SDR原则)可得到最优排序。

证明：在定理1的证明中，因为得出：

以及

由此可得：以及

因此：当时，有，证毕。

定理4：对于问题，如果任意的工件都满足时有，将工件按照非减的顺序排列(即：WSDR原则)可得到最优排序。

证明：由定理1的证明可知在排序和排序下工件和工件的完工时间分别为：

因此只需证明即可。

因为，，，并且，有：

所以：

即：

所以：，证毕。

定理5：对于问题如果工件的恶化率与工期是同序的，即任意的工件都满足时都有。则将工件按照非减的顺序排列(即：EDD原则)可得到最优排序。

证明：在定理1证明中陈述的排序和排序下工件和工件的延误时间分别为：

；

；

如果，则即：

由定理1知，，那么有：

即：

即：

因此：，证毕。

4. 结论

本文讨论了同时带有学习效应、恶化效应以及非线性安装时间和送出时间的单机排序问题。工件的安装时间和送出时间不仅与工件的加工位置有关，还依赖于已加工完成工件的实际加工时间。证明了最小化完工时间问题、最小化总完工时间问题以及最小化总完工时间次方之和问题按照SDR原则即可得到最优排序。同时证明了加权完工时间问题和最大延误时间问题在满足某些条件下多项式时间可解。对于带有学习效应、恶化效应以及非线性安装时间和送出时间的其他目标函数，如：极小化TADC和TADW问题也正在研究中。