生产调度问题和优化算法

《生产调度问题和优化算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD格式可编辑编号：第六届计算机仿真大赛参赛作品题号:加工调度问题组别：高年级组作者：厚玉伟学院：光电工程联系电话：18716321594计算机仿真大赛组委会专业知识分享WORD格式可编辑2012年05月01日生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际

2、。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。专业知识分享WORD格式可编辑二．模型假设1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断；2．所有机器均同时开工，且工件从机

3、器I到机器J的转移过程时间损耗不计；3．各工件必须按工艺路线以指定的次序在机器上加工多次；4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。三．符号说明及初始数据表达分析-第i个工件（i=1…6）-机器顺序阵表示i工件的第j个操作的机器号-第j台机器（j=1…4）-工件排列阵表示i机器上第j次加工的工件号-加工时间阵为i工件的第j个操作的时间周期-整个任务完成时间整理数据后得到：=[CABCD000]=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDA

4、CD0][1048412610][ABACDACA][14735258]上述二阵直接从题目得出，而则是我们要求的。关于工件的加工时间表：(表二)产品/工件（i）:123456总计总净加工时间（周期）441653544535247加工工序总数（个）54567835关于机器的加工时间表：(表三)机器/设备(j):ABCD总计总净加工时间60427075247加工操作次数10610935专业知识分享WORD格式可编辑分析：由于各产品总净加工时间和各机器总净加工时间之中最大值为75，而总计为247，那么总时间C介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理

5、的调度排序是对于节省时间和资源是必要的。希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D不间断工作,直至全部加工任务完成。四．贪婪法快速求解如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:1.优先选择总剩余时间或总剩余操作较多的工件。（如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。2.机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。首先按照

6、最优化时间为75的设想避免D出现等待，排序后得到升以下具体排列顺序。各机器承担任务表为(其中粗体字为对应工件产品号，括号内为对应时间周期段)：操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6(1)2(2-5)1(12-13)6(14-20)3(21-35)4(36)5(43-54)6(55-56)3(57-64)6(66-73)B4(1-7)6(8-11)5(12-15)1(16-19)3(36-55)2(56-58)C3(1-3)1(4-11)4(12-17)5(18-25)6(26-28)1(29-52)5(55-60)6(61-65)2(66-69)4(70-

7、72)D5(1-10)3(11-17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)(表四)专业知识分享WORD格式可编辑(图一)上图为加工周期图（甘特图），标注数字为相应操作的周期，完工时间为第75周期。五．计算机随机模拟（编程）1．编码：随机产生生产的工序操作优先顺序，进行编码，如：K=[43566231416354536641551326224415665]（注：同时作为下文的染色体之用）意