王申重,杜海龙

(郑州大学西亚斯国际学院文理学院,河南新郑 451150)

具有学习效应和遗忘效应的单机排序问题研究

王申重,杜海龙

(郑州大学西亚斯国际学院文理学院,河南新郑 451150)

研究了目标函数为加权总完工时间且具有学习效应和遗忘效应的单机间歇批排序问题.当加工时间和权重存在一致性时研究了三种情形，给出了相应的多项式时间算法.

学习效应；遗忘效应；多项式时间算法①

0 引言

从20世纪50年代开始，排序问题都是众多学者和专家研究的热点问题.在传统的排序问题中，工件加工时间都是固定的，不受加工位置和开工时间等各种因素的影响.但是在生产实践中，机器或工人长时间加工相同或类似的工件，速度会变得越来越快，这样后面工件的加工时间可能会越来越短，这就是所谓的“学习效应”.

Bisbup[1]在1999年首次在排序问题研究中引入了学习效应，并提出了工件的实际加工时间和加工位置有关系的单机排序模型.Liu和Sun等[2]在2003年研究了当工件的正常加工时间和权重存在一致性时对极小化总完工时间的单机排序问题给出了最优算法.Kuo和Yang等[3]在2006年研究了和开工时间有关的学习效应模型，并对相同的问题给出了最优算法.Yang和Kuo等、王吉波等多位学者将学习效应继续应用于间歇批的单机排序研究中，得到了许多结论和成果.娄敏等[4]在2011年研究了具有学习和遗忘效应的单机间歇批排序问题，对两类问题给出了最好算法.杨明……