速度相同的具有m-2台通用机的两组工件的LS算法分析精选.pdf

第49卷第6期 中山大学学报(自然科学版) 场f49Nn6 1 ACTASCIENTIARUMNATURALIUMUNIVERSITATISSUNYATSENINOV．20lO 2010年1月 速度相同的具有m一2台通用机的 两组工件的LS算法分析+ 丁 伟 (中山大学数学与计算科学学院，广东广州510275) 摘 要：对于实践中存在的具有两组任务的优化排序问题进行了讨论，在经典的Ls算法的基础上提出了一种 改进的LS算法，利用“首先空闲”准则选择机器，按照工件的到达顺序安排工件，讨论了将两组工件安排在两 台速度相同的专用机，m一2台同速度的通用机上的c一问题，其中工件具有准备或到达时间，且工件的准备或 到达时间均不超过其加工时间的Ot倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所 得的解7“与最优解r’的一个估计(1十a)(2一l／m)，并且证明了对任意的“此界是紧的。 关键词：启发式算法；性能指标；Ls算法；LFrr算法；通用机与专用机 中图分类号：0223文献标志码：A 文章编号：0529—6579(2010)06—0001—05 An ofLS forthe Problemonm——2 AnalysisAlgorithmScheduling andTwo TaskswithUniformProcessors General·PurposeMachineryGroup DINGWei ofMathematicsand (School Science， Computational SunYat—sen 5 University，Guangzhou10275，China) Abstract：The on withm一2 machineriesandtwo C—problemtwo—groupjobs general—purpose special— machineriesthat arethesame the havethe timesanditisnomored purpose they speed，andjobs setup timethanits timesisstudied．An LS andthe bound processing improvedalgorithm uppertight perform- 8aceare ratioofthe solutionT蝤andthebest given．The approximate way anditis for tightalla． words：heuristic Key approach：performanceindexes；LSalgorithm；Uyr and special—purposemachinery 对于将rt个工件J={J，，12，…，．，。}安排在m用LS(List 台平行机M={M，，鸭，…，M。}上加工，并且工件算法在最差情形下的性能指标为2—1／m；而运用 ^紧跟在‘，。后加工，需要埘(i，_『)的准备时间或唧(LongestProcessingTime)算法，他得到一个 者调整时间，目标是使得所有工件尽早完工