两台流水机器协调分解调度问题-控制与决策.pdfVIP

第 24 卷 第 1 期 控 　制 　与 　决 　策 2009 年 1 月 Vol . 24 No . 1 Cont rol an d D ecis ion 　　J an . 2009 　　文章编号 : 100 10920 (2009) 0 1005506 两台流水机器协调分解调度问题 a ,b a a 关 　静 , 唐立新 , 宋国骄 (东北大学 a . 信息科学与工程学院 , b . 教育部流程工业综合自动化重点实验室 , 沈阳 110004) 摘 　要 : 研究钢管加工流程中一类新型两台机器流水车间调度问题 ,工件在第一台机器上加工后被分解成多个子工 件. 对于最小化最大完成时间的情况 ,给出一个多项式时间的最优算法 ;对于最小化最大完成时间与惩罚费用之和的 情况 ,给出一个拟多项式时间的动态规划算法 ;对于考虑生产前运输的最小化最大完成时间的情况 ,分析了问题的复 杂性. 证明了第一种情况的最优算法可作为后两种情况的2近似算法. 数值实验表明了算法的有效性. 关键词 : 流水机 ; 调度 ; 分解 ; 算法复杂性 ; 动态规划 ; 界分析 中图分类号 : TP29 　　　　文献标识码 : A Two machines flowshop schedul ing problem with disintegration consideration a ,b a a GUA N J i ng , TA N G L ix i n , S ON G Guoj i ao (a . College of Information Science and Engineering , b . Key L aboratory of Int egrat ed for Automation for t he Process Indu st ry of Mini st ry of Education , Nort hea st ern U niver sit y , Shenyang 110004 , China . Correspondent : TAN G L i xin , Email : qhj ytlx @mail . neu . edu . cn) Abstract : A new t yp e of twomachine flow shop scheduling p roblem i s st udied . J ob s are di sint egrat ed into subj ob s on t he fir st machine . For t he scenario when minimizing t he maximum comp letion time a s t he obj ective , we p rovide a polynomial time op timal algorit hm . For t he scenario when minimizing t he sum of maximum completion time and p enalit y co st a s t he obj ective , we p ropo se a p seudopolynomial dynamic algorit hm . For t he scenario wit h inbound t ran sport ation con