具有恶化工件的不同工期指派问题研究

《具有恶化工件的不同工期指派问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第30卷第5期2013年10月沈阳航空航天大学学报JoumalofShenyaIlgALerospaceuIliVers时V01．30No．50ct．20l3厂+。+。+”+。、}基础科学}k。+。+。+。+．』文章编号：2095—1248(2013)05一0083—05具有恶化工件的不同工期指派问题研究王吉波h，岫，一，刘璐h，许扬韬h，郭倩h(1．沈阳航空航天大学a．经济与管理学院；b．理学院，沈阳1l叭36；2．机械制造系统工程国家重点实验室(西安交通大学)，西安710053)摘要：排序问题是机械制造业、计算机系统、管理科学中的一类重要问题。研究具有恶化工件的单

2、机排序问题，其中恶化工件指的是工件的实际加工时问是其开工时间的线性递增函数且所有工件的恶化率相同。每个工件具有不同的工期，且为决策变量。目标是确定所有工件的一个排序和每个工件的工期使得目标函数为提前成本、延迟成本和工期机会成本的加权和最小。证明该问题的算法复杂性是多项式时间可解的，并给出了如何求解该问题的最优算法。关键词：排序；单机；恶化工件；工期；算法中图分类号：0223；C934文献标志码：Adoi：10．3969／j．issn．2095一1248．2013．05．叭7Researchonthedue-datesassig砌entproblemwithdeteri

3、oratingjobsWANGJi-b018，16’．，LIULula，XUYallg．ta01a，GUOQiaIll8(1．a．schoolofEconoIllicsaIldManagement，b．schoolofScience，shenyaIlgAemspaceuIlivers埘，Shenyang110136)；2．StateKeyLaboratoryforManuelct嘶ngSystemsEngineemgⅪ’a11JiaotongUIliVersity，Ⅺ7an710053)Abstract：ScheduhngisaIliInportantpaninmaI

4、lufactIlmgindusny，computersystemsandmanagementsci。ences．In“spaperwestudymesiIlgle—machinedue—datesassignmentscheduhngwimdeterioratingjobs，whichmeaIlsmatmeactualpmcessingtiInesofjobsaredefinedbyincreasiIlgfunctionofmeirstaningtimesa11dⅡ1edet舒om廿ngratesofa11jobsareidentical．Associatedwi出e

5、achjobtllereisaduedate，a11dadeci-sionv撕able．1．IleobjectiveistodeteⅡIlinetlleoptimalscheduleaIlddue—datessimultaIleouslytoIniIliIllizemesumofealliness，tardinessandduedates．WeV嘶fymattlleproblemofdeteriorationcaIlbesolVedinpolynomialtime，aIldwealsopmVideap01ynomialtimealgodmmt0solVemeprobl

6、em．Keywords：scheduling；sin出e—maclline；de￡ed嘞tingjobs；due—date；algo五t11m在制造业系统、计算机系统和管理科学中，排序问题是一类重要的组合优化问题，多年来人们一直致力于该问题的研究¨J。在经典排序问题中，工件的加工时间为常数，但在许多实际问题中，工件的加工时间可能与其开工时间有着某种联系，由此产生一些新型排序问题。这类问题在钢铁工业，塑料工业，军事以及医疗等方面有着广泛的体现。如在军事方面，当天气渐渐变坏或者天色渐渐变黑时，探测目标开始的时间越晚则所花费的时间就越长；在消防工程中，救火的开始时间一旦被耽

7、搁，火势就会难以控制，这样救火的时间将会变长，所付出的代价也会变大(Gawiejnow—icz‘2])。收稿日期：2013—06一06基金项目：国家自然科学基金项目(项目编号：11001181)；辽宁省高等学校优秀人才支持计划资助项目(项目编号：u啦011014)；机械制造系统工程国家重点实验室开放课题(项目编号：sklms201306)作者简介：王吉波(1975一)，男，博士后，教授，主要研究方向：生产计划与排序的研究，E—mail：w∞自ib075@163．com。沈阳航空航天大学学报第30卷Gupta和Gupta¨1与Browne和Yechia