遗传算法求解一类带工艺约束的并行机调度问题

《遗传算法求解一类带工艺约束的并行机调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华中科技大学硕士学位论文遗传算法求解一类带工艺约束的并行机调度问题姓名：陈皓申请学位级别：硕士专业：系统工程指导教师：陈铁英20050829摘要作业车间调度问题JSSP是一类典型的生产调度问题具有很强的工程背景许多实际工程问题均可与之相转化近年来随着先进制造技术的发展车间调度问题的含义有所拓展增加了随机性动态性不确定性约束性多目标等与实际生产更为接近JSSP属于NP完全类因此开发求解JSSP的有效算法一直是调度和优化领域的重要课题并行机调度(ParallelMachineScheduling,PMS)是现实生活中厂矿企业经常面临的一类问题一个作业

2、分成几道工序来完成它允许工序由一个机床集合中的任意一台加工调度的目的是将工序分配给各机床并对各机床上的工序进行排序以使完成所有工序的时间最小化遗传算法是基于优胜劣汰适者生存的一种高度并行随机和自适应优化算法它将问题的求解表示成染色体的适者生存过程通过染色体群的一代代不断进化包括复制交叉和变异等操作,最终收敛到最适应环境的个体从而求得问题的最优解或满意解GA原理和操作简单通用性强不受限制性条件的约束且具有隐含并行性和全局解空间搜索能力在机器学习模式识别控制工程VLSI设计等领域,尤其是在生产调度领域得到广泛的应用如何利用GA高效求解JSP,一直被认

3、为是一个具有挑战意义的难题并成为研究的热点本文主要针对一个具体的生产调度实例采用自己的编码形式来求解从结果来看此方法简单易行收敛快适用范围广是完全可行的一种求解方法遗传算法已经成功应用于组合优化问题如TSP于是很多研究人员想到用遗传算法这种搜寻技术来解决调度问题并行机调度工序时允许工序由一个机床集合中的任意一台加工机床集合一般由工艺约束决定而这更符合生产实际情况并行机调度比一般调度问题复杂因为前者不仅要决定怎样把各工序分配到机器上还要实时确定每台机器的工序操作次序本文的目的就是试图用遗传算法来解决一类带工艺约束的并行机调度问题II现代生产系统运行

4、管理的核心是生产计划与调度理论和技术由于工业生产系统运行管理复杂的特点故其生产计划调度与控制十分重要它对降低生产成本缩短制造周期提高生产效益均具有重要的意义生产调度问题是一个资源分配问题只不过这里的资源是设备而已一个调度是按先后顺序条件将所有任务安排到设备上的一种方案通常约束的数目很大使得生产调度问题成为一个非常难解的NP完全问题随着问题规模的扩大生产调度算法的复杂性呈指数增长目前一般都选用启发式调度规则进行生产实时调度由于调度规则是基于经验故没有普遍适用的规则存在某一规则只能运用于一定的场合应用调度规则求得的解也只是问题的近似解很难保证其解的有

5、效性关键词并行机调度遗传算法作业车间调度IIIAbstractThejobshopschedulingproblem(JSSP)isakindoftypicalproductiveschedulingproblem,andithasafullbackgroundofengineering-basedprojectwhichcanusuallybeconversedtoappliedprojectproblems.Recently,accordingtothedevelopmentofadvancedtechnicalsupport,themean

6、ingofjobshopschedulingproblemshaschangedalot:stochastic,dynamic,bounded,multi-object,thesewordsareaddedontodescribeit.Parallelmachinescheduling(PMS)takesplaceusuallyinafactoryenvironmentwheredifferenttasksmustbeprocessedtocompleteajob.Anumberofjobsarebeingprocessedatanyonetim

7、eonanumberofmachines.Aschedulingmustbederivedfromagivenproductionconfigurationthataimstofinishalljobsasrapidaspossible.ThejobshopschedulingproblemhasbeenstudiedfordecadesandknownasanNP-hardproblem.Theparalleljobshopschedulingproblemisageneralizationoftheclassicaljobscheduling

8、problemthatallowsanoperationtobeprocessedononemachineoutofasetofmach