平行机上工件有到达时间的在线和半在线排序问题

摘要

排序问题是经典组合优化的问题，在线和半在线排序是排序论当前研究的热点问题之一。本文主要讨论工件有到达时间的一些在线和半在线模型，并分析算法下的竞争比。全文共分为三章。
　　 第一章是绪论部分，主要是介绍组合优化中排序问题，竞争比分析和近似算法等基本概念，总结近几年来出现的在线和半在线模型及有关的结论。
　　 第二章考虑同型平行机器上工件到达时间任意且工件加工时间单调不增的问题，目标函数为极小化最大机器负载的在线模型。根据LS算法，证明LS算法的最坏性能比不大于2-1/2m，并且当m=1时，这个界为紧界。
　　 第三章考虑工件到达时间不减，机器加工速度为si=1(1≤i≤m-1)，sm=s＞1的在线排序。目标函数为极小化最大机器负载的在线模型，主要讨论两个问题：1，当m=2时，当其中1台机器的加工速度为1而有一台机器的加工速度为s＞1时，证明LS算法的最坏性能比不大于2；2，当其中m-1台机器的加工速度为1而有一台机器的加工速度为s＞1时，证明LS算法的最坏性能比不大于min{1+sm/s+m-1，2+m-1/s+m-1}。

目录

文摘

英文文摘

声明

1绪论

1.1组合优化简介

1.2排序问题

1.3近似算法

1.4论文概述

2同型机上工件有到达时间且加工时间不增的半在线排序

2.1引言

2.2 Pm||Cmax问题

3同类机上工件到达时间不减的在线排序

3.1引言

3.2 Qm||Cmax问题

3.3 Q2||Cmax问题

结束语

参考文献

致谢