订单在线排序问题的算法设计与分析

摘要

在这篇论文中，我们主要讨论了具有到达时间和加工时间的工件在m台相同平行机上的半在线加工排序问题，分析了LS算法的最坏性能比。其目标函数是要令所有机器的最大完工时间达到最小。若工件序列L={J1,J2，…，Jn}中的工件满足到达时间非递减，加工时间非递增，那么(V)m∈N+，我们证明了LS算法的最坏性能比的上界为3/2-1/2m。而当m=2时，我们证明了LS算法的最坏性能比等于7/6。全文共分四章。
　　第一章是绪论部分，介绍了阅读本文所需的预备知识和基本概念，包括组合最优化问题，近似算法，排序问题以及LS算法。章节末尾介绍了本文的研究模型
　　第二章证明了在m台相同的平行机上，当工件满足到达时间非递减，加工时间非递增时，LS算法的最坏性能比的上界为3/2-1/2m。
　　第三章证明了在两台相同的平行机上，当工件满足到达时间非递减，加工时间非递增时，LS算法的最坏性能比等于7/6

目录

摘要

第一章 绪论

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

§1．2 排序问题简介

§1．3 离线、在线和半在线问题简介

§1．4 LS算法介绍

第二章 m台机器上LS算法的性能比

§2．1 引言

§2．2 引入的符号

§2．3 定理及证明其所需的引理

§2．4 定理2．1的证明

第三章 两台机器上LS算法的性能比

§3．1 引言

§3．2 引入的符号

§3．3 定理3．1及证明其所需的引理

§3．4 定理3．1的证明

第四章 小结

参考文献

致谢

声明