带学习遗忘效应和序列依赖准备时间的无等待流水调度优化方法

《带学习遗忘效应和序列依赖准备时间的无等待流水调度优化方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第l章绪论时间的一个简单线性函数，他们证明最小化makespan和totalflowtime仍然是多项式可解的，但是最小化maximumlateness不一定是多项式可求解。Kuo和Yangl21】建立一种基于加工时间和的学>--j效应模型Pi，．=pi(1+∑：：三jptkl)。，其中A，表示任务五在位置7'调度时的实际加工时间，Pi表示任务五的初始加工时间，Plkl任务表示在位置k调度时的初始加工时间，OL<0表示学习因子，作者阐明了最小化totalflowtime在该模型下是多项式可解的，但是这个模型有个缺点：任务的实际加工时间依赖于已经加工过任务的初始加工时间，这并不符合实际场景。所以

2、Kuo和Yang[22】在此基础上进行了改进，提出一种基于实际加工时间和的学习模型Pir=pi(1+∑七r：--1l碓1)8。Cheng、Wu和Lee[23】结合了Biskup[131的基于位置的学习模型Pi，=p／ra和Koulamas、Kyparisis[24】基于总加工时间的学习模型阱frl=阱(1一阜翘})“，建立一种基于位置以及加工时间和⋯’D‘=lrtt⋯_的学习模型岛，=pj(1一锶Otlr∞，其中Otl≥l和＆2<0表示两种学习因子，功表示任务^的初始加工时间，Pffl表示任务在位置2调度时的初始加工时间，该模型中任务的实际加工时间是一个关于己加工过任务的初始加工时间总和以及任

3、务调度位置的函数。作者证明了在该模型下最小化makespan和totalflowtime的单机调度问题是多项式可解的，最小化maximumlateness和总加权完工时间在特定条件下也是多项式可解的。Janiak和Rudel[25】向调度领域引入了新的学习效应模型，该模型以两种方式来扩展现有的方法：首先放宽了约束条件，在该模型中，每个任务可以为机器提供不同的学习经验；其次把机器的加工时间建模成一个非递增的k-段分段函数，一般情况下这个分段函数不局限于某个具体的学习曲线，因此它可以准确地满足各种可能的学习效果。作者阐明了在该模型下，如果每个任务提供给机器相同的学习经验，那么最小化makespan

4、是多项式可解的；如果提供不同的经验，则是NP．难问题。Janiak和Rudel[26】建立一种基于经验的“s”型学习效应模型pj(v)=0j—bJ(min(v一1，缈))q。Cheng、Kuo和Yang[27】建立一种基于加权位置的学习效应模型功，=pj(1+∑_Icr-：jWkPlk])。r0，其中a≤0是基于总加工时间的学习因子，b≤0表示基于位置的学习因子，p『嘲是任务在位置k调度时的初始加工时间，u七>0是与位置k相关的权值。作者对最小化makespan和totalflowtime单机调度问题给出了优化算法。Lee和Chung[2别提出一种分支限界算法和两种启发式算法Ⅳ鼬EH+P卜SA

5、来求解带学习效应的流水调度问题。Wang等人【29】提出一种指数学习效应模型Pijr=阢，(Qo∑：iwilPilll+卢)6r-1并采用两种启发式算法NEH和LS来求解最小化makespan、total(weighted)completiontime、totalweighteddiscountedcompletiontime的流水调度问题。Behnamian和zandiehl30】建立一种基于位置的学习效应模型以=磋×(t)∥以及提出一种新型混合元启发式算法HMH(粒子群优化算法PSO、模拟退火算法SA和变邻域搜索算法VNS的组合)来求解最小化earliness和tardiness的具有序列

6、依赖准备时间的混合流水调度问题。与学习效应相比，调度问题中考虑遗忘效应的研究相对较少。Teyarachakul[3l】给出了Wright和“S”型遗忘曲线，分别如图1．3和1．4所示。从图1．3可以看出任务加工时间随着时间增加呈现指数增加的趋势：从图1．4可以看出“S”型遗忘曲线也包括三个阶段：1)初始阶段，由于经验已经非常成熟，遗忘对任务加工时间影响甚微；2)遗忘阶段，由于长时间没有加工类似任务，导致经验遗忘迅速，任务加工时间3第1章绪论任务加工时间时间图1．3Wright遗忘曲线任务加工时间时间图1．4“S”遗忘曲线有显著增加；3)稳定阶段，由于经验几乎全部遗忘，任务加工时间无限趋近于初始

7、加工时间。Lee[32】考虑具有学习和遗忘因素的单机调度问题并建立两种学习遗忘效应模型Pi，，=OLttra和Pi。，=(po+啦t)r。，其中Oli表示任务五的遗忘因子，Q表示学习因子，踟和t分别表示任务五的初始加工时间和开始时间，作者证明了最小化makespan和totalflowtime在该模型下是多项式可解的。Wang[8】建立一种基于位置的学习遗忘效应模型Pi^r=(olij+／3t)r