生产调度问题是自动化管理领域中一个十分重要的问题,而单件车间(Job-Shop)调度问题是一个实际的生产调度问题。单件车间调度算法是当前调度理论的重要研究内容之一,此项研究既可以促进调度理论的发展及其相关问题的研究,又可以使企业实现生产计划的动态调整。 Job-Shop调度问题是一类具有次序约束和资源约束的组合优化问题,是一个典型的NP难题,而非标准Job-Shop调度问题,由于放宽了资源约束的条件,因而具有更大的寻优空间,从而增加了问题的难度。理论上已经证明要在多项式时间复杂度内对这一类问题找到全局最优解是不可能的。本文通过对Job-Shop调度问题和非标准Job-Shop调度问题的深入分析和研究,根据问题的特点,提出了两种适用于工程实际的算法——基于剩余函数的Job-Shop调度算法和非标准Job-Shop调度的效率算法,它们均可以在多项式时间复杂度内寻得较优解。论文分别从以下几方面进行论述。 首先,论文对调度问题及其研究现状进行全面综述,阐述基于剩余函数的Job-Shop调度算法以及非标准Job-Shop调度的效率算法的优越性。 其次,论文给出基于剩余函数的Job-Shop调度算法以及非标准Job-Shop调度的效率算法的详细描述,包括Job-Shop调度问题和非标准Job-Shop调度问题在数学上的描述、目标函数、算法描述和调度实例。 最后,论文根据生产中的实际情况,提出一类更实际的调度问题——多部套相关工件的Job-Shop调度问题,并给出求解算法。