工件有长度约束时LPT算法的性能分析

摘要

在这篇论文中，主要讨论了具有相似加工时间且加工时间非递增的工件在2台同类型平行机上的离线加工排序问题，分析了LPT算法的最坏性能比.其目标函数是要令所有机器的最大完工时间达到最小.若工件序列L={J1，J2，…，Jn}中的工件满足pj∈[1，r](r≥1)且p1≥p2≥…≥pn,，当m=2时，证明了LPT算法的最坏性能比为R(2,LPT)={7/6,r≥3/2,kr+k+1/2k+1,1+1/2k-2/2k(2k+3)≤r≤1+1/2k,4k+7/4k+6.1+1/2k+2≤r≤1+1/2k-2/2k(2k+3),1,r=1当11/8≤r≤3/2时，得到的性能比和文章[1]的结果一样.当r＜11/8时，得到的最坏性能比比文章[1]的结果更小且是紧的. 文章的第一章为绪论，介绍了阅读本文所需要的预备知识和基本概念，包括组合优化问题，近似算法，排序问题，LS以及LPT算法. 文章的第二章，证明了具有相似加工时间且加工时间非递增的工件，在2台同类型平行机上的LPT算法的最坏性能比. 文章的第三章，总结了整篇文章以及对未来工作的建议.

目录

摘要

第一章绪论

1．1组合优化问题及近似算法简介

1．2排序问题简介

1．3在线、离线及半在线问题

1．4 LS及LPT算法简介

第二章两台机器上LPT算法性能分析

2．2引入的符号

2．3定理及其证明

第三章小结

参考文献

致谢

声明