有尺寸的同型机分批排序问题的近似算法

《有尺寸的同型机分批排序问题的近似算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第22卷第1期2013年2月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．22，No．1Feb．2013有尺寸的同型机分批排序问题的近似算法吴翠连1，陈俊2(1．曲阜师范大学管理学院，山东日照276826；2．泰山职业技术学院信息工程系，山东泰安271000)摘要：对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法。对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形，利用动态规划的方法和拆分的技巧，我

2、们设计了近似算法并分析了其最差性能比。关键词：组合最优化；分批排序；近似算法；动态规划；最差性能比中图分类号：0224文章标识码：A文章编号：1007—3221(2013)01—0077—06SchedulingJobswithNon-identicalSizesonParallelBatchProsessorsWUCui—lianl，CHENJun2(1．CollegeofManagement，Q咖NormalUniversity，R如hao276826，China；2．Dept．ofInformationEngineer-ing，Tai

3、ShanVocational&TechnicalCollege，Taian271000，China)Abstract：WestudytheproblemP。tB，0，SjCmaxfortheversionwheretheprocessingtimesoflargejobs(withsizesgreaterthanhalfthecapacityofmachine)arenotlessthanthoseofsmalljobs(withsizesnotgreaterthanhalfthecapacityofmachine)．Themethodsa

4、ppliedinthispaperarescaling—and-roundinganddynamicpro—gramming．AnaIgorithmispr。p。sedwithworst-caserati。—_3+s．Keywords：combinatorialoptimization；parallelbatchprosessors；algorithm；dynamicprogramming；worst—caseratio0引言排序问题一直是运筹学领域里一类重要问题，在生产管理、调度、网络通讯以及计算机科学中都有着广泛的应用背景，发挥着巨大的

5、作用。排序问题又称调度问题，是指给指定的若干机器和一组工件以及某个目标函数，按照一定的要求合理地将这些工件分配到机器上，给每台机器上的工件安排一个加工顺序以及相应的开工时间，使得给定的目标函数达到最优。这里机器和工件都是抽象的概念，因为排序领域中许多早期的工作是在制造业的的推动下发展起来的，所以描述排序问题时自然会使用制造业的术语，虽然排序问题在许多非制造业领域内取得了相当有意义的成果，但制造业的术语一直在使用¨1。因而，往往把资源(Resource)称为机器(Machine)，把任务(Task)称为工件(Job)。分批排序问题主要产生于大

6、规模的现代化生产流水作业线如半导体生产、航空工业和钢铁铸造等。这方面的研究工作于上世纪九十年代很快地发展并活跃起来，最富有代表性的应是等旧’31。随着半导体工业的飞速发展以及竞争的不断加剧，如何有效的利用组合优化的工具，提出好的算法以缩短产品的生产流程，提高生产效率，具有重大意义。一般情况下，我们要求体积大的工件的加工时间不小于体积小的工件的加工时间是合理的”1。本文收稿日期：2011-08—08基金项目：国家自然科学基金资助项目资助(11071142)作者简介：吴翠连(1977．)，女，硕士，讲师，研究方向：运筹学78运筹与管理2013年

7、第22卷考虑这种情形下09分批排序问题是有意义的。我们定义：当工件体积大于机器容量的÷时为大工件，否则二为小工件。若每一个大工件的加工时间不小于任何一个小工件的加工时间，我们称此类工件为工时与体积成比例。我们考虑的是工件工件的工时与尺寸成比例的条件下目标函数为极小化最大完工时间的同型机分批排序问题。所谓的同型机(IdenticalParallelMachine)是指，工件在每台机器加工所需要的加工时间都相同即每台机器的加工速度都一样。这个问题用三参数表示法记作：P。IB，rJ，s，fc⋯。问题可描述为：设有n个工件．，i(J=1，2，⋯，n

8、)要在m台机器上加工，其到达时间、加工时间和体积(size，很多文献也译作尺寸)分别为rt，pi，st。其中，5，是整数且0