车间作业调度问题是一类重要的组合优化问题，生产生活中许多问题都可以抽象为车间作业调度问题。同时，车间作业调度问题的求解在理论研究中也是重要的研究方向。对车间作业调度问题进行精确求解已经被证明是NP-完全问题。进化算法是一类模仿生物进化行为的随机优化算法，这种算法理论上能跳出局部最优，并且对问题模型的依赖小，能有效弥补传统优化方法的不足。当前，用进化算法求解车间作业调度问题是热门的研究课题。本文首先用多步交叉遗传算法求解车间作业调度问题。本文的算法基于经典遗传算法和局部搜索方法的结合，算法中交叉算子不再是经典遗传算法中父代解的直接交叉，而是将父代解作为局部搜索的初始值进行迭代，经过局部搜索得到新一代的解。进而，把车间作业调度问题的可行解用析取图编码，并相应定义了可行解之间的析取图距离，AS型邻域和CB型邻域。其次用离散粒子群优化算法求解车间作业调度问题。本文在粒子群优化算法的迭代方程中引入了随机因子，从而增强了粒子种群的多样性。并借鉴经典遗传算法中交叉和变异的思想实现了粒子的运动。进而，用双向量对车间作业调度问题进行编码，将离散粒子群优化算法应用于车间作业调度问题的求解。最后用实验结果比较了经典遗传算法，多步交叉遗传算法和离散粒子群优化算法在求解车间作业调度问题的效果。