作业车间调度问题是公认的最难的组合优化问题之一，也是一个典型的NP 难度问题。研究作业车间调度问题具有很高的理论价值。同时，作业车间调度问题是实际工业生产调度问题的抽象表述，不仅可以应用于生产调度方面，而且可以应用在经济管理、交通运输以及网络通讯等各个领域。所以，对作业车间调度问题的研究也具有很高的实际意义。　　 数十年来，国内外的许多学者对作业车间调度问题进行了深入研究，提出了许多算法。用精确算法求解该问题时，计算时间随着问题规模的增大呈指数级增加，其实际价值并不大。因此，设计高效的求解作业车间调度问题的启发式算法成为当前研究的重点。　　 针对作业车间调度问题，提出了一种高效的解的可行性判定算法T。用该算法对8组不同规模的国际标准算例进行了测试，并与基于深度优先遍历思想的判定算法DFS算法进行了比较。实验结果表明，T算法的效率比DFS算法要高很多。　　 设计了一种新的邻域结构和一种有效的搜索机制，形成了混合邻域搜索算法DSP。该算法能够防止搜索过早的卡壳在局部最优的陷阱。DSP算法采用了一种新的优先指派算法Vip—SP 来生成初始解。同时，采用了T算法对解进行可行性判断，效率提高了很多。用该算法计算了42个国际标准算例。实验结果表明，该算法是一种高效的启发式算法。