车间作业调度(Job Shop Problem)是一类典型的NP-hard 问题,已被证明在多项式时间内得不到最优值。该问题是生产管理中的核心问题,好的求解方法可以促进企业提高生产率。因此,该研究无论从理论还是实际都有重要意义。近年来,对于JSP 问题的求解主要有启发式算法和元启发式算法,但各有其不足之处:元启发式方法的运行时间长,可获得较好的解,但其解不稳定;启发式方法可在较短的时间内得到鲁棒性较强的解,但是极少获得较优的解。为了更好地解决问题,将一些解决某类问题较好的算法组合起来,使所形成的混合算法具有两者不可比拟的优势,成为目前研究的热点。本文分别应用病毒遗传算法和混合遗传算法来求解车间作业问题JSP(Job Shop Problems)。针对遗传算法求解的早熟和收敛速度慢等问题,提出面向车间作业调度的病毒遗传算法JVGA(Job shop oriented Virus Genetic Algorithm),从横向和纵向同时搜索解空间;并提出一种新的病毒浓度概念不仅可以增强病毒群体模式的多样性还可以定量地评价染色体中某段基因的数量,克服了遗传算法固有的早熟问题;其次,定义了基于工件序的十进制编码方式,既避免了死锁的产生也便于解空间和染色体空间转换。根据19 个典型JSP 问题的对比实验,证明了该理论对于求解JSP 问题的有效性。遗传算法初始解的质量对于算法的收敛速度有重要的影响,将解决JSP较理想的改进瓶颈移动启发式算法MSB 得到的解作为遗传算法的一个初始解,主群体中其它体随机产生,提出混合遗传算法HGA(Hybrid Genetic Algorithm)。由于MSB 所得解的质量较高,而GA 算法的精英策略保证HGA 所得解的质量不低于MSB 算法所得解的质量。两种算法的结合,使算法的时间性能有较大的提高。