两台机器流水作业中带成组加工的最大迟后问题.PDFVIP

第 22卷 第 2期 应 用 科 学 学 报 Vo1．22，No．2 2004年 6月 jouRNALOFAPP1IEDSCIENCES June2004 文章编号：0255—8297(2004)02—0247—05 两台机器流水作业中带成组加工的最大迟后问题 陈 跃，孙世杰，宋政芳，何龙敏 (上海大学 数学系，上海 200436) 摘 要 ：考虑分批加工 中的流水作业问题 ：且工件在两台机器间作成批转移 ，目标函数为 厶…．文中指出该 问题为 NP—hard后给出了其多项式可解的特例并构造了相应的动态规划算法． 关键词 ：排序 ；批处理机 ；最大迟后 ；强NP—hard；多项式可解 中图分类号：0223 文献标识码 ：A M inimizingtheM aximum LatenessonaTwoM achineFlowshop withBatchProcessors CHEN Yue， SUN Shi—jie， SONGZheng—fang， HELong—min (DepartmentofMathematics，ShanghaiUniz，ersity，Shanghai200436，China) Abstract：Thispaperconsidersthefollowingproblem： jobsneedtobeprocessedontwoma— chines( 1， )successively．ThedeadlineforjobJisd，，andtheprocessingtimesofjobJon 1， M2areaJ， ，respectively．Bothmachinesarebatchprocessors．Thismeans，2jobsare groupedintoseveralbatchesonM，，i一1，2，respectively，andthemachinesprocessthejobsin samebatchsimultaneously．Theprocessingtimeofabatchisequaltothelongestprocessingtime ofallthejobsinthisbatch．Thusallthejobsinsamebatchareprocessedinthesamelengthof timeonthegivenmachine，andthejobswillbealsoshiftedinbatches．Wetakethemaximum latenessasourobjecfunctionforminimization．Afterpointingoutthatthisschedulingproblem is NP—hard。wegivesomespecialcasesthatcanbesolvedinpolynomialtimeandconstructthecor— respondingdynamicprogramming． Keywords：scheduling；batchprocessor；maximum lateness；strongNP—hard；polynomialtime algorithm 本文考虑下述存在分批加工的流水作业问题 ： 批方式可以不同．用三参数表示法_l】将此类问题记 个工件需要依次在机器M ，M 上加工．工件 j=的应 为：F2(B ，B)1BIl厂，其中B ，B 分别是M。，M 上 交工时间为 ，，其在机器 ， 上的加工时间分别 的每批工件数的上界，若无上界则取o。，BI指 Burn 为a，，6，．机器 ，一1，2依成批方式加工，即 个 In，因为此种加工方式常出现在半导体元件老化测 工件在机器 上分成若干批