单位工件的平行机并行分批在线排序问题的算法

《单位工件的平行机并行分批在线排序问题的算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２４卷第１期运筹与管理Ｖｏｌ．２４，Ｎｏ．１２０１５年２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＦｅｂ．２０１５单位工件的平行机并行分批在线排序问题的算法胡丹，农庆琴，方奇志（中国海洋大学数学科学学院，山东青岛２６６１００）摘要：本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J＝｛J１，…，Jn｝要在m台批处理机上加工。批处理机每次可同时加工至多B（B＜n）个工件。同一批中的工件同时开工，同时完工，工件加工过程不允许中断。工件Jj（１≤j≤n）的到达时间为rj，加工时间为１，工件是否会到达

2、事先未知，而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题，本文设计了两个竞争比均达到最好可能的在线算法。关键词：排序；并行批；最大完工时间；在线算法；竞争比中图分类号：Ｏ２２５文章标识码：Ａ文章编号：１００７－３２２１（２０１５）０１－０１３７－０５AlgorithmsforanOnlineParallel－batchingSchedulingProblemwithUnitJobsＨＵＤａｎ，ＮＯＮＧＱｉｎｇ－Ｑｉｎ，ＦＡＮＧＱｉ－Ｚｈｉ（SchoolofMathematicalScience，OceanUniversi

3、tyofChina，Qingdao２６６１００，China）Abstract：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｃｏｎｓｉｄｅｒｔｈｅｐｒｏｂｌｅｍｏｆｏｎ－ｌｉｎｅｓｃｈｅｄｕｌｉｎｇａｓｅｔｏｆｉｎｄｅｐｅｎｄｅｎｔｊｏｂｓJ＝｛J１，…，Jn｝ｏｎｐａｒａｌｌｅｌ－ｂａｔｃｈｉｎｇｐｒｏｃｅｓｓｉｎｇｍａｃｈｉｎｅｓ｛M１，…，Mm｝．ＥａｃｈｍａｃｈｉｎｅｃａｎｈａｎｄｌｅｕｐｔｏBｊｏｂｓａｓａｂａｔｃｈｓｉｍｕｌ－ｔａｎｅｏｕｓｌｙ，ａｎｄａｌｌｔｈｅｊｏｂｓｉｎａｂａｔｃｈｓｔａｒｔａｎｄｃｏｍｐｌｅｔｅａｔｔｈｅｓａｍｅｔｉｍｅ．Ｏｎｃｅａｂａｔｃｈｉ

4、ｓｓｔａｒｔｅｄ，ｉｔｃａｎｎｏｔｂｅｓｔｏｐｐｅｄｕｎｔｉｌｉｔｓｃｏｍｐｌｅｔｉｏｎ．Ｗｅｄｅａｌｗｉｔｈｔｈｅｂｏｕｎｄｅｄｃａｓｅｗｈｅｒｅｔｈｅｃａｐａｃｉｔｙｏｆｔｈｅｍａｃｈｉｎｅｓｉｓｆｉｎｉｔｅ，ｉ．ｅ．，B＜n．ＥａｃｈｊｏｂJj（１≤i≤n）ｂｅｃｏｍｅｓａｖａｉｌａｂｌｅａｔｉｔｓｒｅｌｅａｓｅｄａｔｅrj，ｗｈｉｃｈｉｓｕｎｋｎｏｗｎｉｎａｄｖａｎｃｅ，ａｎｄｉｔｓｐｒｏ－ｃｅｓｓｉｎｇｔｉｍｅpjｉｓａｕｎｉｔｔｉｍｅ．Ｔｈｅｐｒｏｂｌｅｍｉｎｖｏｌｖｅｓａｓｓｉｇｎｉｎｇａｌｌｔｈｅｊｏｂｓｔｏｂａｔｃｈｅｓａｎｄｍａｃｈｉｎｅｓａ

5、ｎｄｄｅｔｅｒｍｉ－ｎｉｎｇｔｈｅｓｅｑｕｅｎｃｅｏｆｂａｔｃｈｅｓｓｏａｓｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｋｅｓｐａｎ（ｔｈｅｍａｘｉｍｕｍｃｏｍｐｌｅｔｉｏｎｏｆｔｈｅｊｏｂｓ）．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｗｏｄｉｆｆｅｒｅｎｔｂｅｓｔｐｏｓｓｉｂｌｅｏｎ－ｌｉｎｅａｌｇｏｒｉｔｈｍｓ，ＵｎｉｆｉｅｄＡｌｇｏｒｉｔｈｍａｎｄＧｒｅｅｄｙＡｌｇｏｒｉｔｈｍａｒｅｄｅｓｉｇｎｅｄ．Keywords：ｓｃｈｅｄｕｌｉｎｇ；ｐａｒａｌｌｅｌ－ｂａｔｃｈｉｎｇ；ｍａｋｅｓｐａｎ；ｏｎ－ｌｉｎｅａｌｇｏｒｉｔｈｍ；ｃｏｍｐｅｔｉｔｉｖｅｒａｔｉｏ０引言分批排序问题是排序论

6、的一个重要分支，兴起于９０年代初应用背景极强的一类最优化问题。它的研究结果主要应用于大规模的现代化生产流水作业线如半导体生产、航空工业、钢铁铸造、制鞋业等等，研究并行分批排序问题具有十分重要的实际意义。并行分批排序可以描述为：有n个相互独立的工件J＝｛J１，…，Jn｝待加工，工件Jj（１尘j尘n）的到达时间记为rj，加工时间记为pj。有m台批处理机｛M１，M２，…，Mm｝，批处理机每次可同时加工至多B（B称为机器的批容量）个工件，加工时间不同的工件可作为一批来加工，批的加工时间是此批中工件的加工时间的最大者。同一批中工件同时开工、同时完工。注意到当B＝１时，此问

7、题即为经典排序问题。分批排序打破了经典排序一台机器在同一时间只能处理一个工件的约束，是经典排序问题的一种推广。根据批容收稿日期：２０１２－０８－２９基金项目：国家自然科学基金资助项目（１１２０１４３９）；国家自然科学基金资助项目（１１２７１３４１）；教育部博士点专项基金新教师基金（２０１２０１３２１２０００１）；山东省自然科学基金（ＺＲ２０１２ＡＱ１２）作者简介：胡丹（１９８９－）女，硕士研究生，研究方向：组合最优化；农庆琴（１９７８－）女，副教授，博士，研究方向：组合最优化，排序；方奇志（１９６６－）女，教授，博士，研究方向：组合最优化，计算复杂性。１３８运筹

8、与管理２０１５年第２４卷