Single machine scheduling problem with interval processing times to minimize mean weighted completion time
Single machine scheduling problem with interval processing times to minimize mean weighted completion time
复制标题
DOI：
10.1016/j.cor.2014.06.003
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
A. Allahverdi;H. Aydilek;Asiye Aydilek
中科院分区：
文献类型：
--
作者：
A. Allahverdi;H. Aydilek;Asiye Aydilek
单资源调度问题不仅适用于只有单一资源的实际生产系统，也适用于只有一种资源瓶颈的多资源生产系统。因此，单资源(机器)调度问题在调度文献中得到了广泛的解决。研究了加工时间不确定的区间单机调度问题。目标是最小化平均加权完工时间。这个问题已经在文献中得到了解决，并提出了有效的启发式算法。本文利用处理时间的界，提出了一些新的多项式时间启发式算法。通过大量的计算实验对提出的启发式算法和现有的启发式算法进行了比较。所进行的实验除了文献中使用的受限实验之外，还包括一个通用的模拟环境和几个额外的代表性分布。结果表明，所提出的启发式算法的性能明显优于现有的启发式算法。具体地说，最佳性能启发式算法将文献中的最佳现有启发式算法的误差降低了75%以上，而最佳性能启发式算法的计算时间少于最佳现有启发式算法。此外，最优启发式的绝对误差仅为最优解的1%左右。绝对误差非常小，计算时间可以忽略不计，这表明了所提出的启发式算法的优越性。
The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.