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

肄蕿螈膈生产调度问题及其优化算法螃(采用遗传算法与MATLAB编程)蕿腿蚅薁虿蕿莇信息014孙卓明蚄蝿二零零三年八月十四日蚆螅莃生产调度问题及其优化算法衿肇背景及摘要蒇这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序,而且工序的变更又可能导致相当大的调度规模。解空间容量巨大,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***8芄(表一)袁条件:1、每件产品必须按规定的工序加工,不得颠倒;虿2、每台设备在同一时间只能担任一项任务。羆(每件产品的每个工序为一个任务)莄问题:做出生产安排,希望在尽可能短的时间里,完成所接受的全部任务。节要求:给出每台设备承担任务的时间表。肇蚅注:在上面,机器A,B,C,D即为机器1,2,3,4,程序中以数字1,2,3,4表示,蒄说明时则用A,B,C,,每台机器只能加工一个工件,且每个工件只能被一台机器所加工,同时加工过程为不间断;,且工件从机器I到机器J的转移过程时间损耗不计;;,即前一操作未完成,则后面的操作需要等待,可用资源有限。-第i个工件(i=1…6)羈-机器顺序阵表示i工件的第j个操作的机器号芅-第j台机器(j=1…4)蚄-工件排列阵表示i机器上第j次加工的工件号蚁-加工时间阵为i工件的第j个操作的时间周期蒆-整个任务完成时间肄整理数据后得到:肈=[CABCD000]=[824246000]肂[ADBC0000][45340000]蒂[CDABA000][3715208000]肇[BCDADC00][7621116300]***[DBCDACD0][1048412610]蒃[ABACDACA][14735258]袀上述二阵直接从题目得出,而则是我们要求的。肀关于工件的加工时间表:(表二)***产品/工件(i):袄1薂2衿3芇4芅5肀6蚈总计莇总净加工时间(周期)蚆44螁16蚁53蒇54螃45蒃35葿247薇加工工序总数(个)膃5羁4芈5蚇6薄7蚃8羇35螇羅关于机器的加工时间表:(表三)肁机器/设备(j):肀A螆B肂C袃D蝿总计袆总净加工时间薃60芁42薈70羆75羄247羃加工操作次数薁10肆6薂10蚈9薇35莄羃分析:莀由于各产品总净加工时间和各机器总净加工时间之中最大值为75,而总计为247,那么总时间C介于[75,247]。同时各工件加工繁杂程度不一,各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。莆希望最优化答案是75,这样达到最小值,如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。,当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:。(如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析)。,尽量避免等待空闲时间,优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。蒁