工件有到达时间排序问题的LS算法分析

工件有到达时间排序问题的LS算法分析

    排序问题是组合优化领域中的一类重要问题，它是利用一些处理机、机器或者资源，最优地完成一批给定的任务或作业，在生产管理与调度、网络通信、理论计算机科学等方面有广泛的应用。 本文主要研究在m台同型机上工件有到达时间的排序问题的LS算法。目标函数是使机器的最大完工时间（makespan）达到最小。 第一章介绍了排序问题，算法的竞争比分析等基本概念，描述了（半）在线排序和工件有任意到达时间的在线排序模型的一些特性。第二章研究了m台同型机上有到达时间工件的LS排序问题，研究了LS算法的最坏性能比。给出了LS算法的紧性能比的一个简单证明。第三章讨论了m台同型机上工件有到达时间且加工时间非增的LS算法问题，得到如下的两个结论，一个是证明了对于任意工件序列L={J1，J2，…，Jn）如果 r1≤r2≤…≤rn且P1≥P2≥…≥Pn，有R（m，LS）≤3/2-1/2m；另一个是若到达时间为任意的且加工时间为单调非增序列，则LS算法的最坏性能比不大于2。
 

请继续阅读相关推荐：毕业论文    应届生求职

毕业论文范文查看下载      查看的论文开题报告     查阅参考论文提纲

查阅更多的毕业论文致谢    相关毕业论文格式       查阅更多论文答辩

【工件有到达时间排序问题的LS算法分析】相关文章：

GPRS问题的分析与解决论文04-27

萨克斯教学中的问题分析论文05-05

详谈改进的遗传算法求解柔性作业车间调度问题论文04-26

简述时间名词的范畴问题论文06-05

转换分析问题加强数学思维训练05-08

关于问题儿童出现的原因分析08-17

供电企业电力营销管理问题分析05-02

库存管理机制问题分析论文04-28

素描教学存在的问题及对策分析的论文06-09

企业激励管理存在问题分析论文04-19