两类极小化最大加权完工时间排序问题研究-论文.pdf

《两类极小化最大加权完工时间排序问题研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第32卷第3期佛山科学技术学院学报(自然科学版)VO1．32NO．32014年5月JournalofFoshanUniversity(NaturalScienceEdition)Mav2Ol4文章编号：1008—0171(2014)03—00l8—03两类极小化最大加权完工时间排序问题研究臧西杰，李士生(1．郑州大学数学与统计学院，河南郑州450001；2．中原工学院理学院．河南郑州450007)摘要：研究两个单机排序问题。目标函数均是最大加权完工时间对于问题lIII~IXW证明了1w规则序是最优排序，而问

2、题lIrlmaxwf．用3-划分问题归结。证明是强NP困难的。关键词：最大加权完工时间；排序；到达时间；Lw规则；强NP困难中图分类号：0223文献标志码：A排序论，又称为时间表理论，在自动化学科中称为调度论，是运筹学的一个活跃分支，有重要的理论价值和广泛的应用背景[1]。作为一类重要的组合优化问题，排序论的研究从20世纪50年代初期开始，产生的背景主要是机械制造业，目前在农业、制造业、运输物流、管理、计算机等多个领域中均有应用【3]。近几十年来，排序理论发展迅速，新的模型和研究方法不断涌现]。关于极小化最

3、大完工时间和加权总完工时间的问题有很多研究。李曙光等考虑无界批量机器并行调度中极小化加权完工时间问题，给出了一个多项式时间近似方案(PTAS)。古春生等l_『针对柔性flowshop加权完成时间调度问题，通过对机器环境进行分组，证明了一个基于有效作业最短加权平均处理时间的启发式算法是渐近最优的。冯大光等[7提出了工件分批的最优性质，利用工件最优分批性质进行分批，提出了两种启发式算法。张树霞等L8针对目标函数是有限的总惩罚费用，设汁了伪多项式时间的动态规划算法，并给出了相应的FPTAS算法。然而，对于极小化最

4、大完工时间这一类有着广泛应用的问题，涉及到的研究却很少。本文研究两个单机排序问题，目标函数均是最大加权完工时间。实际生产中，每个工件的紧急程度不同，定义紧急工件的权重大于一般工件的权重，显然最优序中紧急工件应尽早安排、完工，这样目标函数达到最优。例如银行为提高效率，设置了对公窗口、VIP窗口，对这样的客户，银行优先提供服务。笔者对于问题l}Imaxzvc，，证明了Iw规则序是最优排序，而问题l}r，flllaXZ~a，c，，用3-l戈U分问题归结，证明是强NP困难的。定义l将工件1，2，⋯，／'7按叫非增的

5、顺序排列的排序规则称为最大权优先规则，简称Iw规则。在IW规则之下，将工件1，2，⋯'，f重新标号，使得W。≥删≥⋯≥。目标函数为极小化最大加权完工时间时，设最优序为丌。1模型定理1对于问题1llmaxzu，c，Lw规则序是最优排序。证明若中工件全部按Iw规则排序，则定理1得证。若存在一个最优序玎，其中的工件不是和7f中一样按Iw规则排序。设I，是在丌中不按Iw规则收稿日期：2013—12—23基金项目：国家自然科学基金数学天元基金资助项目(n326191)；河南省自然科学基金资助项目(1323004103

6、92)作者简介-：臧酉杰(1979一)，男，河南郑州人，中原工学院讲师。第3期臧西杰：两类极小化最大加权完工时间排序问题研究l9排序且具有最小下标的工件，L厂为丌中排在L厂之前且离工件，最近的工件．且．≥叫。新排序丌是将丌中工件和，，对换所得，其他工件相对位置不变。"LUf，(Tr)≤"cO(7r)，，(丌)≤(7r)，其他工件目标函数均保持不变，所以．对换工件L，和后得到的新排序丌所对应的目标函数值不会比原排序中更大，丌也是最优排序。经过有限次的对换，得到一个最优排序丌按Iw规则排序。定理2排序问题1fF

7、naxzeJc是强NP困难的。证明排序问题的判定问题显然在NP类。为了证明问题的强NP困难性，用强NP完全的3l划分问题I9来归结。3t3一划分问题：对给定的3t的整数(-11，⋯，，其中∑口一ty且y／4<“

8、一(f一1)(+1)／j(：1，⋯，t一1)，，．一0(—t，⋯，4f一1)，户一a¨l(=t，⋯，4一1)，u，，=(￡一1)(十1)／(ty十t一1)(—t，⋯，it～1)，Y一(f一1)(+1)。显然，上面的构造过程可以在多项式时间内完成。如果3一划分问题有解，可以将a”，a3t重新标号，使得a，+一3+口f+一2+a卜一l=Y对一切1≤≤f成立。下面证明3-划分问题的实例有解当且仅当对问题1I，．Imax