The Supply Chain Scheduling Problem Based on Truncated Learning Effect and Time Dependence

本文假定：n个工件J₁，J₂，…，J_n在同一台机器上进行加工，每次只能加工一个工件且在加工过程中不能中断；每个工件J_j有正常加工时间p_j、权重w_j、工期d_j和配送时间q_j；工件J_j的实际加工时间为p_jr(t)=p_jα(t)max{r^a，b}，其中t为工件J_j的开工时间，r为工件J_j在加工序列中的位置，α(t)为开工时间t的非增凸函数且满足0 < α(t)≤1，α(0)=1，α′(t) < 0，a < 0为学习效应，b为给定的参数且0 < b < 1.工件配送时间q_j采用Koulamas^[6]中的模型，即第r位工件的配送时间为q_r=$c\sum\limits_{l = 1}^{r{\rm{ - }}1} {p[l]} $，p_[l]为排在第l位工件的正常加工时间且c≥0，简记为q_psd.符号C_j和L_j表示工件J_j的完工时间和延迟，C_max=max{C_j|j=1，2，…，n}表示最大完工时间，L_max=max{L_j=C_j-d_j|j=1，2，…，n}表示最大延迟.本文所研究的模型如下：

利用简单的数学计算可以得到如下引理1：

引理1  设$\lambda {\rm{ = }}\frac{{\max \left\{ {{{\left( {r + 1} \right)}^a}, b} \right\}}}{{\max \left\{ {{r^a}, b} \right\}}}$，a < 0，0 < b < 1，则0 < λ≤1.

引理2^[10]  设α(t)是非增可微凸函数且α^′(t)在[0，+∞)上是非减函数，则当0 < k≤1，0 < λ≤1，m > 0，t₀ > 0时，(k-1)α(t₀)+λα(t₀+mk)-λkα(t₀+m)≤0成立.

引理3^[10]  设α(t)是非增可微凸函数且α^′(t)在[0，+∞)上是非减函数，则当0 < k≤1，0 < λ≤1，m > 0，0 < λ₁≤λ₂ < 1，t₀ > 0时，(k-1)α(t₀)+λλ₁α(t₀+mk)-λλ₂kα(t₀+m)≤0成立.

定义1^[10]  反一致关系：工件J_j的正常加工时间和权重满足p_i≤p_j⇒w_i≥w_j.

定义2^[10]  一致关系：工件J_j的正常加工时间和工期满足p_i≤p_j⇒d_i≤d_j.

定理1  对于模型(1)，工件按照p_j非减的顺序(SPT)排列即为最优序列.

证  假设S₁：π₁→J_i→J_j→π₂是满足p_i≤p_j的序列，交换工件J_i和J_j得到S₂：π₁→J_j→J_i→π₂，π₁和π₂表示部分序列且π₁中有r-1个工件，且第r个工件开工时间为t₀.则有

故有

令

则0 < k≤1，m > 0.由引理1，2知0 < λ≤1，

所以C_j(S₁)≤C_i(S₂).工件J_i和J_j前面的工件在其交换位置后完工时间没有改变，工件J_i和J_j后面的工件在其交换位置后开工时间没有变小，所以工件按照p_j非减的顺序(SPT)排列即为最优序.

定理2  对于模型(2)，工件按照p_j非减的顺序(SPT)排列即为最优序.

证  类似于定理1，假设S₁：π₁→J_i→J_j→π₂和S₂：π₁→J_j→J_i→π₂.在p_i≤p_j的条件下只需证C_j(S₁)≤C_i(S₂)和C_i(S₁)+C_j(S₁)≤C_i(S₂)+C_j(S₂)即可.由定理1可知C_j(S₁)≤C_i(S₂)，又p_i≤p_j，则

成立，故

即工件按照p_j非减顺序(SPT)排列为最优序.

注意到经典的WSPT序并不能产生模型(3)的最优序列.接下来利用WSPT序作为启发式算法，给出了最坏竞争比分析如下：

定理3  对于模型(3)，将WSPT序排列所得序列和最优序列分别表示为π和π^*，且在零时刻开工，则模型(3)的最坏竞争比分析为

且这个界是紧的.

证  记π：π(1)→π(2)→…→π(n)和π^*：π^*(1)→π^*(2)→…→π^*(n)，设p_[i]和p_π(i)表示π中第i个工件的正常加工时间和实际加工时间，p_[i]^*和p_π^*(i)表示π^*中第i个工件的正常加工时间和实际加工时间，则

进一步得

其中C_π^*为定理1中的最大完工时间.

由于0 < max{r^a，b}≤1，0 < α(t)≤1，下面证明这个界是紧的.如果max{r^a，b}=1(b→1)和α(t)=1，WSPT序即为模型(3)的最优序列，因此这个界是紧的.

尽管经典的WSPT序规则不能得到模型(3)的最优解，但可以证明加工时间和权重满足反一致关系时，模型(3)仍然可以得到多项式时间算法.

定理4  对于问题模型(3)，当工件的正常加工时间和权重存在反一致关系即p_i≤p_j⇒w_i≥w_j时，按照$\frac{{{p_j}}}{{{w_j}}}$非减的顺序WSPT排列即为最优序.

证  若S₁：π₁→J_i→J_j→π₂是满足$\frac{{{p_i}}}{{{w_j}}} \le \frac{{{p_j}}}{{{w_j}}}$的序列，交换工件J_i和J_j得一新序S₂：π₁→J_j→J_i→π₂，π₁中有r-1个工件，且第r个工件的开工时间为t₀.则有

令

由引理1和引理3可知

故当满足反一致关系时按照$\frac{{{p_j}}}{{{w_j}}}$非减的(WSPT)排列即为最优序.

由定理4易知下面推论1成立.

推论1  对于问题模型(3)，当工件的权重和加工时间成比例时，p_j非减的排列顺序(SPT)即为最优序.

类似可知经典的EDD序规则不能得到模型(4)的最优序列.为了得到当前问题的最坏竞争比分析，需要重新定义最坏竞争比函数为

其中d_max=max{d_j|j=1，2，…，n}，π和π^*表示EDD序列和最优序列.

定理5  对于模型(4)，将按照EDD序排列所得序列和最优序列分别表示为π和π^*，在零时刻开工，则

且这个界是紧的.

证  记π：π(1)→π(2)→…→π(n)和π^*：π^*(1)→π^*(2)→…→π^*(n)，设p_[i]和p_π(i)分别表示π中第i个工件的正常加工时间和实际加工时间，p_[i]^*和p_π^*(i)分别表示π^*中第i个工件的正常加工时间和实际加工时间.

其中C_max^*为定理1中的最优时间表长.

由于0 < max{r^a，b}≤1，0 < α(t)≤1，当max{r^a，b}=1(b→1)和α(t)=1时EDD序即为模型(4)的最优序列，因此这个界是紧的.

尽管经典的EDD序规则不能得到模型(4)的最优解，但可以证明加工时间和工期满足一致关系时，当前模型仍然是多项式时间可解的.

定理6  对于模型(4)，当正常加工时间和工期存在一致关系时，按照d_j非减的顺序(EDD)排列即为最优序.

证  若S₁：π₁→J_i→J_j→π₂是满足p_i≤p_j⇒d_i≤d_j的序列，交换工件J_i和J_j得一新序S₂：π₁→J_j→J_i→π₂，π₁中有r-1个工件，且第r个工件的开工时间为t₀.则有

由定理1，2可知max{L_i(S₁)，L_j(S₁)}≤max{L_i(S₂)，L_j(S₂)}，L_max(S₁)≤L_max(S₂)成立，交换工件J_i和J_j最大工期不会变小，所以当满足一致关系时按照d_j非减的顺序(EDD)排列即为最优序.

由定理6易知下面推论2和推论3成立.

推论2  对于模型(4)，如果工件的加工时间都相同，工件按照d_j非减的顺序(EDD)排列即为最优序.

推论3  对于模型(4)，如果工件的工期都相同，工件按照p_j非减的顺序(SPT)排列即为最优序.

下面给出3个算例来验证上面所给出的结论的合理性和正确性.

假设p_jr(t)=p_jα(t)max{r^a，b}里α(t)=1-0.02t，a=-0.5，b=0.75，c=0.1，在零时刻开始加工.

例1  n=5，p₁=4，p₂=2，p₃=6，p₄=8，p₅=10，对C_max和${\sum C _j}$，按照SPT序排列5个工件得到S₁：J₂→J₁→J₃→J₄→J₅，计算可得C₂=2，C₁=5.08，C₃=9.54，C₄=15.07，C₅=21.29，则有C_max(S₁)=21.29，${\sum C _j}$ (S₁)=52.98.交换一下J₁和J₂，得一新序S₂：J₁→J₂→J₃→J₄→J₅，计算可得C₁=4，C₂=5.78，C₃=10，C₄=15.47，C₅=21.63，则有C_max(S₂)=21.63，${\sum C _j}$ (S₂)=56.88.由上面结果可知C_max(S₁) < C_max(S₂)，${\sum C _j}$ (S₁) < ${\sum C _j}$ (S₂).

例2  n=5，p₁=4，p₂=2，p₃=6，p₄=8，p₅=10，w₁=4，w₂=5，w₃=3，w₄=2，w₅=1，对${\sum {{w_j}C} _j}$，按照WSPT序排列5个工件得到S₁：J₂→J₁→J₃→J₄→J₅，计算可得C₂=2，C₁=5.08，C₃=9.54，C₄=15.07，C₅=21.29，则有${\sum {{w_j}C} _j}$ (S₁)=110.37.交换一下J₁和J₂，得一新序S₂：J₁→J₂→J₃→J₄→J₅，计算可得C₁=4，C₂=5.78，C₃=10，C₄=15.47，C₅=21.63，则有${\sum {{w_j}C} _j}$ (S₂)=127.47.由上面结果可知${\sum {{w_j}C} _j}$ (S₁) < ${\sum {{w_j}C} _j}$ (S₂).

例3  n=5，p₁=6，p₂=4，p₃=9，p₄=12，p₅=15，d₁=4，d₂=3，d₃=9，d₄=10，d₅=14，对于L_max，按照EDD序排列5个工件得到序列S₁：J₂→J₁→J₃→J₄→J₅，计算可得C₂=4，L₂=1，C₁=8.54，L₁=4.54，C₃=14.79，L₃=5.79，C₄=22.21，L₄=12.21，C₅=30.09，L₅=16.09，则有L_max(S₁)=16.09.交换一下J₁和J₂，得一新序S₂：J₁→J₂→J₃→J₄→J₅，计算得C₁=6，L₁=2，C₂=9.24，L₂=6.24，C₃=15.22，L₃=6.22，C₄=22.56，L₄=12.56，C₅=30.36，L₅=16.36，则有L_max(S₂)=16.36.从上面结果可知L_max(S₁) < L_max(S₂).

本文研究了基于截断学习效应和非增函数的时间相关的供应链单机排序模型.工件的实际加工时间是截断学习效应及位置有关凸函数.首先给出了多项式时间算法.对于一般情形，利用经典的WSPT序，EDD序作为启发式算法给出了最坏竞争比分析.