作业加工调度问题不仅是NP难的,还被认为是最难的组合最优化问题之一.已经知道,为解决工业生产、经济管理和网络通讯等诸多方面的问题,都要借助于求解这个问题.优质、快速地求解作业加工调度问题,既有重要的理论意义,又能带来巨大的经济效益.转换瓶颈程序(SB)是一个很有代表性的求解作业加工调度问题的启发式算法.但是它遇到一个困难,就是它不能够得到某些实例的可行解.以此为切入点,一个很有力的定理在此被证明,它部分地解决了SB算法的这一困难.而且,基于这个定理,一个新的启发式算法——改进的转换瓶颈程序(ISB)被提出来.该算法继承了SB的"转换瓶颈机"的思想,然而放松了界定瓶颈机的条件,就是不要求每一台机器的排序是最优的.上述定理的推论表明,ISB不会遇到与SB相同的困难.对大量实例的计算结果表明,ISB算法在计算速度和所得到的解的优度上几乎都优于SB算法.在所采用的48个实例中,ISB有29个的解优于SB,而SB只有2个的解优于ISB.ISBB是ISB的一个改进版本,它是将ISB与回溯算法结合起来而得到的,ISBB优于SB的第二版本SBII.在这48个实例中,ISBB有18个的解优于SBII,而SBII只有在9个的解优于ISBB.虽然与新近的某些算法相比,ISB和ISBB的性能不是足够高,但是它们可以作为很好的求解作业加工调度问题的基本算法.在已有的求解作业加工调度问题的诸多启发式算法中,禁止(Tabu)搜索算法以其高效性而倍受人们重视.HLS是结合ISB算法和Tabu搜索算法所得到的一个新的混合式邻域搜索算法.它采用ISB算法来产生初始解,这使得它的初始解比其它的邻域搜索算法的优.HLS还采用新的搜索技术以改进Tabu搜索算法的两个很重要的搜索策略——集中搜索策略和分散搜索策略.SHLS是对HLS进行另外一种改进的结果.它将一种随机策略引入HLS之中,每次从若干台"准瓶颈机"中随机选取一台来作为当前瓶颈机,并对此机器所加工工序的次序进行重新排列.用这种办法来降低对瓶颈机的限制条件,以期最终消除瓶颈机的概念.从大量的模拟计算来看,SHLS实现了初步目标,在计算效率与所得解的质量上,它优于一个典型的模拟退火算法LAL,并且达到了算法NS(1)的水平.