调度是决策的一种形式,它在制造业和服务业中扮演着关键角色。生产调度是实现制造业运筹、管理与优化技术的核心,它是在时间上对一组可用的制造资源进行加工任务的安排,将工件分配至相应的机器上,确定各机器上操作的加工次序和开工时间,使得某一性能指标最优。生产调度问题可以抽象描述为在一些等式或不等式约束构成的离散解空间中,寻找目标函数的最优解。它是一类重要的组合优化问题,运筹学称之为排序问题。除少数特殊问题,大部分生产调度问题的计算复杂度为NP-hard。有效的优化调度能使生产和商业领域增加产出、减少周转时间、减少库存,最终减少生产费用、增加利润和客户满意度。 作业车间调度问题是所有生产调度中最复杂、最困难,也更具一般性的问题。本文在对作业车间调度问题作细致分析并建立数学模型的基础上,研究了作业车间调度的若干关键问题。其相关工作主要集中在具有复合邻域结构的禁忌搜索方法研究和设计；两个特定机器和工作环境下的调度问题研究及其解决方法；符合车间调度遗传算法的三维染色体编码研究；遗传算法控制参数的优化选取等。旨在夯实本领域的研究基础,为求解作业车间调度问题提供新的有效解决思路,开辟新的研究方向等。所完成的工作和取得的成果具体如下。 1、就生产调度问题的定义与描述作了重点探讨,结合Graham等人提出的生产调度问题分类和描述法,给出了生产调度问题的三元组α｜β｜γ描述方法,这种方法使复杂生产调度问题的描述变得条理化、简约化。 2、Van Laarhoven等人提出的邻域结构具有连通性,但解数量非常大,而Nowichi等人设计的邻域结构具有邻域规模小的特点,但不具有连通性。本文结合以上两种邻域结构的优势和同时避免其不足,提出了一种基于具有复合邻域结构的禁忌搜索算法,并在证明了复合邻域结构具有连通性的基础上,对算法的有效性作了多方面的验证。 3、对于无等待作业车间调度问题J｜no-wait｜Cmax,首先利用三划分问题的强NP-hard特性间接证明了本问题的复杂性。然后提出了一种正反排时算法来解决无等待作业车间调度问题的两个子问题之一,并结合解决子问题二的K-邻域禁忌搜索来使问题J|no-wait|Cmax得到解决。其中的正反排时算法开辟了新的解空间,是非延时的排时算法无法抵达的。 4、在通常的作业车间调度问题中引入了加工顺序决定的准备时间和每个操作都有速度不同的多个并行机器可以备选两个约束后,虽然调度目标也是最小化最大制造期,但却没有可行的求解方法。在建立了此问题的混合整数规划模型并研究其调度解编码方法后,本文提出了一种两阶段禁忌搜索算法来求解多约束作业车间调度,该方法同时搜索最好的加工顺序安排和加工每个操作的最佳机器。这是一个很接近现实生产环境的调度问题,但目前对其的研究很鲜见。 5、在使用迭代进化算法解决调度问题时,编码方法是其关键问题,不同的编码需要设计不同的进化算子与之相适应,它们对整个算法的有效性和效率有重大影响。结合已有编码方法和作业车间调度的特点,提出了一种三维染色体编码方法以及与之相对应的遗传进化算子。并与传统的算法比较验证了其有效性和正确性。 6、对于遗传算法、模拟退火、禁忌搜索等具有通用性的算法,在具体运用于实际问题时怎样根据问题上下文设置最优的算法控制参数一直是个公开问题(Open Problem)。当使用遗传算法来解决大规模作业车间调度问题时,本文提出了基于计算量优化分配的算法比较方法来对候选的算法控制参数进行优化决策,选出针对具体问题的最佳算法控制参数,解决算法参数设置的盲目性问题。