论文部分内容阅读
作业车间调度问题不仅是NP难的，而且被认为是最难的组合优化问题之一。这个问题既是人工智能研究领域的问题，又属于管理科学与运筹学领域，也属于计算机科学和应用数学领域。在工业生产、交通运输、经济管理和网络通讯等方面有广泛的应用。优质、快速地求解作业车间调度问题，既有重要的理论意义，又能带来巨大的经济效益。 转换瓶颈(SB)算法是一个有效的、很有代表性的求解作业车间调度问题的启发式算法。但是SB算法有个缺点，就是它在解单机调度问题时，丢掉了一些约束条件，因此可能对解产生负面影响，可能使解的质量下降，更糟糕的是，有时还得不到可行解。SB算法是基于Carlier单机调度算法的，而Carlier算法又是基于Schrage单机调度算法。对此，先证明了以Schrage算法解决单机调度问题的SB算法不会产生不可行解，再给出了以Carlier算法解决单机调度问题的SB算法产生不可行解的实例。在补上单机调度中丢失的约束条件的基础上，提出了一种改进的转换瓶颈算法(MSB）。该算法在解决单机调度问题时采用了改进的Carlier算法，解决了上述SB算法的问题。对一组实例的计算结果表明，MSB算法在计算所得到的解的优度上优于SB算法，也优于另一种改进了的转换瓶颈算法(ISB)。在所采用的42个实例中，MSB有19个的解优于SB，而SB只有5个的解优于MSB。从25个较难LA实例的计算的平均相对误差看，MSB的平均相对误差是3.55，小于SB的5.91，也小于ISB的3.88。虽然与当前最高效的算法相比，MSB的性能还不够高，但是它可以作为很好的求解作业车间调度问题的基本算法。 为了使作业车间调度问题更易理解、更好想，给出了作业车间调度问题的一个新的、直观的描述方法，并以这种描述方法对实数范围内的作业车间调度问题的最优解的存在性做了证明。基于这种描述方法，提出了一种优先指派规则算法A0和一种基于该优先指派规则与前瞻策略的算法A1。对一组实例的计算结果表明，A1算法在所得解的优度上与1999年提出的beam搜索算法相当，计算速度则比beam搜索算法快了40倍以上。 在已经提出的求解作业车间调度问题的各类启发式算法中，局域搜索方法因其高效性而备受重视，而禁忌搜索算法又是局域搜索方法中最有效的算法之一。TTS_R是基于禁忌搜索过程和试探思想的一种新算法，其采用的禁忌搜索过程与1996年以前最有效的算法之一的TSAB算法所采用的禁忌搜索过程类似。为了得到更好的计算结果，TTS_R中还引入了新提出的倒转技术。倒转技术可以用在任何解决作业车间调度问题的近似算法中，使计算结果有可能改善，代价是平均计算时间增加一倍左右。对四十五个标准实例的试验显示，TTS_R算法比TSAB算法计算结果好的实例数是计算结果差的三倍。 作业车间调度问题禁忌搜索过程中邻域的构造通常是基于对关键路径上的边的翻转，而要在邻域中得到比原解更好的解，常常不仅需要对关键路径上的边做翻转，还需要对有关的非关键路径上的边做翻转。为了克服这个缺点，提出了两种新的邻域结构以及相应的两种新的禁忌搜索方法。这两种禁忌搜索方法都采用两个禁忌表分别对两种不同类型的边的翻转做禁忌。还提出了另一种提高计算速度的改进的禁忌搜索方法。在前两种禁忌搜索方法与试探思想的基础上提出了一种新的算法TTS2，在后一种禁忌搜索方法和改变禁忌表长度策略的基础上提出了另一种新的算法VTS。对一组标准实例的试验结果显示，TTS2算法计算结果好于TSAB算法的实例数目是差于TSAB算法的2倍。对41个基准实例的试验显示，VTS算法有10个解的计算结果好于TSAB算法，3个解差于TSAB算法。 当前解决作业车间调度问题的效率最高的启发式算法常常是结合了多种技术的混合式算法。TTSSB是结合了禁忌搜索、试探思想和转换瓶颈方法的一个新的混合式算法。TS&SB和TS&SB1是基于禁忌搜索和转换瓶颈方法的另外两个新的混合式算法，它们都使用不止一种禁忌搜索方法，都采用了一组转换瓶颈过程对禁忌搜索“跳坑”。其中，TS&SB1用了比TS&SB更多的禁忌搜索方法，还采用了倒转技术。对一组标准实例的试验结果显示，TS&SB和TS&SB1计算结果好于当前计算效果最好的算法中的两个——TSSB算法和SB-GLS2算法，TTSSB计算结果好于TSSB算法。