论文部分内容阅读
本文研究工件带到时间的柔性流水作业排序问题。首先介绍了目前平行机排序、流水作业排序以及柔性流水作业排序等问题的研究情况，并在Potts和Lee研究的基础上提出了工件带到达时间的柔性流水作业的排序模型。
我们首先考虑只有2个处理中心的情况，基于求解流水作业和平行机问题的算法思想，提出了两个近似算法H(R)和H(MRJ)，证明了这两个算法的时间复杂度分别为O(nlogn)和O(n3logn)，最坏情况性能比分别为3-1/m和5/2-1/m，讨论了界的紧性，并进行了数值模拟，分析算法的平均性能比。
然后，我们把2个处理中心推广到更一般的具有s个处理中心的情况，并把算法H(R)和H(MRJ)改进为H(R)和H(MRJ)，同时也分析了它们的时间复杂度和最坏情况性能比。