作业车间调度问题(JSSP)是一类典型的生产调度问题,具有很强的工程背景,许多实际工程问题均可与之相转化。近年来,随着先进制造技术的发展,车间调度问题的含义有所拓展,增加了随机性、动态性、不确定性、约束性、多目标等,与实际生产更为接近。JSSP 属于NP 完全类,因此开发求解JSSP 的有效算法一直是调度和优化领域的重要课题。并行机调度(Parallel Machine Scheduling, PMS)是现实生活中厂矿企业经常面临的一类问题,一个作业分成几道工序来完成。它允许工序由一个机床集合中的任意一台加工,调度的目的是将工序分配给各机床,并对各机床上的工序进行排序以使完成所有工序的时间最小化。遗传算法是基于“优胜劣汰、适者生存”的一种高度并行、随机和自适应优化算法。它将问题的求解表示成染色体的适者生存过程,通过染色体群的一代代不断进化,包括复制、交叉和变异等操作,最终收敛到“最适应环境”的个体,从而求得问题的最优解或满意解。GA 原理和操作简单,通用性强,不受限制性条件的约束,且具有隐含并行性和全局解空间搜索能力,在机器学习、模式识别、控制工程、VLSI设计等领域,尤其是在生产调度领域得到广泛的应用。如何利用GA 高效求解JSP,一直被认为是一个具有挑战意义的难题并成为研究的热点。本文主要针对一个具体的生产调度实例,采用自己的编码形式来求解; 从结果来看,此方法简单易行,收敛快,适用范围广,是完全可行的一种求解方法。遗传算法已经成功应用于组合优化问题,如TSP,于是很多研究人员想到用遗传算法这种搜寻技术来解决调度问题。并行机调度工序时,允许工序由一个机床集合中的任意一台加工(机床集合一般由工艺约束决定),而这更符合生产实际情况。并行机调度比一般调度问题复杂,因为前者不仅要决定怎样把各工序分配到机器上,还要实时确定每台机器的工序操作次序。本文的目的就是试图用遗传算法来解决一类带工艺约束的并行机调度问题。