带有递送时间的工期窗口指派排序问题研究

崔 博，王吉波

(沈阳航空航天大学 理学院，沈阳 110136)

在排序模型中，带有递送时间的排序问题受到了广泛关注。Koulamas等[1]引入了依赖过去序列的递送时间这一概念，假设工件的递送时间与等待时间有一定的比例关系，提出带有递送时间的排序问题并应用于电子制造业中，并对单机带有递送时间的极小化工件加工时间表长、最大延迟和最大延误问题给出多项式时间算法。Liu等[2]研究了工件具有准备时间的递送时间单机排序问题，目标是极小化总完工时间。在工件可中断条件下，他们证明了此问题是多项式时间可解的，在不可中断情况下，他们证明了此问题是NP难的，并提出了近似算法求解此问题。Liu等[3]研究了工件具有递送时间单机排序问题，对一些正则和非正则目标函数，他们给出了一些结论。Yang等[4]和Shen等[5]研究了工件加工时间具有学习效应的单机排序问题。Liu[6]研究了带有递送时间和学习效应的平行机排序问题。Yang[7]与 Zhao[8]研究了带有递送时间的单机排序问题，其中工件加工时间是位置的函数。他们证明了一些正则和非正则目标函数问题都是多项式时间可解的。Yang等[9]研究了带有递送时间且具有恶化和学习效应的排序问题。Wu[10]研究了带有递送时间和截断学习效应的单机排序问题，他们证明了极小化时间表长、加权总完工时间和最大延误极小化问题均是多项式时间可解的。

另一方面，在准时制生产过程中，在工期窗口前完工的工件要受到提前惩罚(比如提前完成，顾客还不需要，从而产生存储和人工等费用)，在工期窗口后完工的工件也要受到延误惩罚(比如顾客不满意产生的费用)(Janiak等[11])。……