研究了以作业完成时间之和最小化为目标函数的单机调度问题,该问题中各作业到达时间可能不同。在对传统启发式算法进行分析的基础上,提出一种改进算法,并给出了算例及其计算结果。大量的随机数据实验的结果表明,该改进算法的性能比传统启发式算法的性能更优。
This paper considered the single machine scheduling problem with unequal release dates so as to minimize total completion times. This problem was proved to be as an NP--hard problem. Traditional heuristics for the problem were analyzed,and,then we presented an improved algorithm. A numerical example and its computational result were given. The performance of the algorithm was also analyzed by experiments and the experimental results show that the algorithm is more effective than the existing heuristics.