内容发布更新时间 : 2024/12/23 20:58:12星期一 下面是文章的全部内容请认真阅读。
生产调度问题及其优化算法
(采用遗传算法与MATLAB编程)
信息014 孙卓明
二零零三年八月十四日
生产调度问题及其优化算法
背景及摘要
这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,N个工件、M台机器的问题包含(N!)M种排列。由于问题的连环嵌套性,使得用图解方法也变得不切实际。传统的运筹学方法,即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解,既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法,采用MATLAB软件实现算法模拟,得出优化方案,并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。 对车间调度系列问题的有效解决具有一定参考和借鉴价值。
一.问题重述
某重型机械厂产品都是单件性的,其中有一车间共有A,B,C,D四种不同设备,现接受6件产品的加工任务,每件产品接受的程序在指定的设备上加工,其工序与加工周期如下表:(S-设备号、T-周期) 工序 1 2 3 4 5 6 7 8 产品 S T S T S T S T S T S T S T S T 1 C 8 A 2 B 4 C 24 D 6 2 A 4 D 5 B 3 C 4 3 C 3 D 7 A 15 B 20 A 8 4 B 7 C 6 D 21 A 1 D 16 C 3 5 D 10 B 4 C 8 D 4 A 12 C 6 D 1 6 A 1 B 4 A 7 C 3 D 5 A 2 C 5 A ( 表一 ) 条件:1、每件产品必须按规定的工序加工,不得颠倒; 2、每台设备在同一时间只能担任一项任务。
(每件产品的每个工序为一个任务)
问题:做出生产安排,希望在尽可能短的时间里,完成所接受的全部任务。 要求:给出每台设备承担任务的时间表。
8 注:在上面,机器 A,B,C,D 即为机器 1,2,3,4,程序中以数字1,2,3,4表示,
说明时则用A,B,C,D
- 1 -
二.模型假设
1.每一时刻,每台机器只能加工一个工件,且每个工件只能被一台机器所加工 ,同时加工过程为不间断; 2.所有机器均同时开工,且工件从机器I 到机器J 的转移过程时间损耗不计; 3.各工件必须按工艺路线以指定的次序在机器上加工多次; 4.操作允许等待,即前一操作未完成,则后面的操作需要等待,可用资源有限。
三.符号说明及初始数据表达分析
Ji - 第i个工件 (i=1?6)
(i,j)表示i工件的第 j个操作的机器号 JM- 机器顺序阵 JMMj- 第j台机器 (j=1?4)
MJ- 工件排列阵 MJ(i,j)表示i机器上第j次加工的工件号 T - 加工时间阵 T(i,j)为i工件的第 j个操作的时间周期 C - 整个任务完成时间
整理数据后得到:
= [ 8 2 4 24 6 0 0 0 ]
[ A D B C 0 0 0 0 ] [ 4 5 3 4 0 0 0 0 ] [ C D A B A 0 0 0 ] [ 3 7 15 20 8 0 0 0 ] [ B C D A D C 0 0 ] [ 7 6 21 1 16 3 0 0 ] [ D B C D A C D 0 ] [ 10 4 8 4 12 6 1 0 ] [ A B A C D A C A ] [ 1 4 7 3 5 2 5 8 ] 上述二阵直接从题目得出,而MJ则是我们要求的。
JM=[ C A B C D 0 0 0 ] T关于工件的加工时间表:(表二) 产品/工件(i): 1 44 5 2 16 4 3 53 5 4 54 6 5 45 7 6 35 8 总计 247 35 Ji 总净加工时间(周期) Ji 加工工序总数(个)
关于机器的加工时间表:(表三) 机器/设备(j): A 60 10 B 42 6 C 70 10 D 75 9 总计 247 35 Mj 总净加工时间 Mj 加工操作次数 分析:
由于各产品总净加工时间和各机器总净加工时间之中最大值为 75,而总计为247,那么 总时间 C 介于[75,247]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。
希望最优化答案是75,这样达到最小值,如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。
- 2 -