matlab生产调度问题及其优化算法

matlab生产调度问题及其优化算法

ID:19412326

大小:230.00 KB

页数:13页

时间:2018-09-27

matlab生产调度问题及其优化算法_第1页
matlab生产调度问题及其优化算法_第2页
matlab生产调度问题及其优化算法_第3页
matlab生产调度问题及其优化算法_第4页
matlab生产调度问题及其优化算法_第5页
资源描述:

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

1、生产调度问题及其优化算法(采用遗传算法与MATLAB编程)信息014孙卓明二零零三年八月十四日12生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,N个工件、M台机器的问题包含种排列。由于问题的连环嵌套性,使得用图解方法也变得不切实际。传统的运筹学方法,即便在单目标优化的静态调度问题中也难以有效应用。本文给

2、出三个模型。首先通过贪婪法手工求得本问题最优解,既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法,采用MATLAB软件实现算法模拟,得出优化方案,并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。一.问题重述某重型机械厂产品都是单件性的,其中有一车间共有A,B,C,D四种不同设备,现接受6件产品的加工任务,每件产品接受的程序在指定的设备上加工,其工序与加工周期如下表:(S-设备号、T-周期)工序

3、产品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8(表一)条件:1、每件产品必须按规定的工序加工,不得颠倒;2、每台设备在同一时间只能担任一项任务。(每件产品的每个工序为一个任务)问题:做出生产安排,希望在尽可能短的时间里,完成所接受的全部任务。要求:给出每台设备承担任务的时间表。注:在上面,机器A,B,C,D即为机器1,2,3,4,程序中以数字1,2,3,4表示,说明时则用A

4、,B,C,D12二.模型假设1.每一时刻,每台机器只能加工一个工件,且每个工件只能被一台机器所加工,同时加工过程为不间断;2.所有机器均同时开工,且工件从机器I到机器J的转移过程时间损耗不计;3.各工件必须按工艺路线以指定的次序在机器上加工多次;4.操作允许等待,即前一操作未完成,则后面的操作需要等待,可用资源有限。三.符号说明及初始数据表达分析-第i个工件(i=1…6)-机器顺序阵表示i工件的第j个操作的机器号-第j台机器(j=1…4)-工件排列阵表示i机器上第j次加工的工件号-加工时间阵为i工件的第j个操作的时间周期-整个任务完成时间整理

5、数据后得到:=[CABCD000]=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA][14735258]上述二阵直接从题目得出,而则是我们要求的。关于工件的加工时间表:(表二)产品/工件(i):123456总计总净加工时间(周期)441653544535247加工工序总数(个)54567835关于机器的加工时间表:(表三)机器/设备(j):ABCD总计总净加工时间60427075

6、247加工操作次数10610935分析:由于各产品总净加工时间和各机器总净加工时间之中最大值为75,而总计为247,那么总时间C介于[75,247]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。希望最优化答案是75,这样达到最小值,如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。12四.贪婪法快速求解如果按照一定规则排序,当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:1.优先选择总剩余时间或总剩余操作较多的工件。(如果出现总剩余加工时间多者

7、总剩余操作数反而较少的情况时,按照程度具体情况具体分析)。2.机器方面来说,尽量避免等待空闲时间,优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。首先按照最优化时间为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

8、-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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。