资源描述：
《基于遗传算法的Job_Shop调度问题求解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第9卷第2期软件学报Vol.9,No.21998年2月JOURNALOFSOFTWAREFeb.1998①基于遗传算法的Job-Shop调度问题求解方法陈恩红刘贵全蔡庆生(中国科学技术大学计算机系合肥230027)E2mail:csehchen@comp.polyu.edu.cn摘要调度问题是许多计算机应用领域的重要问题,Job2Shop调度是其中的一类典型的困难问题,它通常包含多个可并行实现的目标以及实现这些目标的多种方法与资源.本文以一类实用的Job2Shop问题模型为基础,给出了用遗传算法求解调度问题
2、应采用的染色体表示方法,并针对问题的特点,给出了面向资源空间与面向规划空间的遗传操作的设计思想与方法.实验结果表明,基于遗传算法的Job2Shop调度问题求解方法具有较好的性能,同时也表明,对于求解过程中可能出现的提前收敛问题可通过改变遗传操作概率及调节适应度等方法予以解决.关键词Job2Shop调度,遗传算法.中图法分类号TP18[1～4]如何有效地解决调度问题是许多计算机应用领域面临的一个困难而重要的问题.典型的调度问题包含多个可并行实现的目标以及实现这些目标的多种方法及资源.目标、方法及资源的组合是问
3、题的状态空间呈指数形式增长.作为调度问题中代表性的Job2Shop调度,其目标是以尽可能少的时间,同时满足其它一些约束条件情况下,将各[4]种操作调度到适当的机器上,分别加工某些构件,最终生产出某种产品.下面是一个反映调度问题一般特征的模型:·每种Job生产一种产品;·每种产品由多个构件组成,每种构件数量若干;·一个Job2Shop可生产多个构件;·每种构件有多种可供选择的生产规划;·每种规划由一系列串行操作构成;·每种操作需要若干资源,如机器等(本文仅考虑这一种);·每台机器可用于不同类型的操作,每种操作
4、可用机器若干台;·每种操作需占用某机器一段时间;·每种Job由一个需求序列组成;·每种需求对应一个构件,即一个产品有多少构件,Job中就有多少种需求.对于某些问题可能还有其它约束.求解这类调度问题就是设法将生产各种构件的操作合理地分配到可供使用的机器上,以求尽可能地提高机器的利用率和构件响应速度.与上述问题模型相关的搜索空间有:需求空间,即各种构件的生产顺序;规划空间,生产每种构件可采用若干种不同的规划实现;资源空间,每种规划中的每种操作都可能在若干种不同的机器上实现.由于每种规划和分配给它的资源联系紧密,
5、所以往往将资源与规划空间作为一个整体来考虑.每种规划实现的可能方法数为规划中每个操作可选择的资源数的乘积,每种构件生产的方法数为生产该构件的规划数之和,由此可知总的规划、资源空间大小可表示如下:npartnplan[i]nop[i,j]---767n-resource[i,j,k]i=1j=1k=1①本文研究得到国家自然科学基金、国家教委博士点基金和中国科学技术大学青年基金资助.作者陈恩红,1968年生,博士,讲师,主要研究领域为遗传算法,机器学习,约束满足问题.刘贵全,1970年生,博士生,主要研究领域为
6、机器学习,知识发现.蔡庆生,1938年生,教授,博士导师,主要研究领域为人工智能,机器学习.本文通讯联系人:陈恩红,合肥230027,中国科学技术大学计算机系本文1997201220收到原稿,1997204203收到修改稿—140—软件学报9卷其中n-part为构件的类数,n-plan[i]表示生产构件i的可能规划数,n-op[i,j]表示生产构件的第j种规划所含操作数,n-resource[i,j,k]为生产构件i的第j种规划中的第k个操作可用的资源数.当一种Job由多种需求组成,每种构件可用多种规划实现
7、,每类操作可选用多种资源时,问题的搜索空间就会呈指数形式增长.由于时间与空间的限制,盲目搜索算法无力求解这样复杂的调度问题,而启发式搜索方法在搜索空间[5～7]太大时也难以奏效.采用遗传算法可在很大的状态空间中随机高效地采样、搜索,并较快地收敛到最优或近似最优解.本文将详细给出基于遗传算法的Job2Shop调度实现方法,最后对该方法的性能进行分析.1基于遗传算法的Job-Shop调度实现1.1染色体的表示方法用遗传算法求解Job2Shop调度问题,首先要为每种Job的调度寻求一种适当的表示方法.通常,染色体
8、表示应遵循两条原则:染色体中每种基因与问题相关而与其它基因无关;选取最小字母表表示问题.对于该问题,一种可能的方法是以每台机器的调度来构造染色体.每台机器的调度用分配到该机器的各种操作表示,操作按时间顺序排列.采用这种表示容易实现染色体适应度的计算,且无须调度生成过程的介入,但相应的遗传操作设计非常复杂.为了充分利用遗传算法的优点,在Job2Shop调度问题中,将资源及规划两种空间都纳入遗传算法的搜索范围,本文采
