%0 Journal Article
%T 工件具有相似加工时长时两台机上<i>LPT</i>算法的性能分析<br>Performance Analysis of <i>LPT</i> Algorithm for Jobs with Similar Sizes on Two Machines
%A 王凤
%A 李荣珩
%A 周云霞
%J Computer Science and Application
%P 1309-1316
%@ 2161-881X
%D 2019
%I Hans Publishing
%R 10.12677/CSA.2019.97147
%X <div style=\"text-align:justify;\">
	<span style=\"font-size:14px;\">本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列<i>L</i>={<i>J</i><sub>1</sub>,<i>J</i><sub>2</sub>,...,<i>J</i><sub>n</sub>}中的工件满足<i>p<sub>j</sub></i>∈[1,<i>r</i>](<i>r</i>≥1)，证明了LPT算法的最坏性能比为r的分段线性函数，此结论改进了已有的最好结论，并且是不能再改进的最好结论。<br />
In this paper, LPT algorithm is considered for the scheduling problem in which the processing times of jobs are similar on two machines. The objective function is to minimize the maximum completion time of all machines. The worst performance ratio of the LPT algorithm is given as a piecewise linear function of r if job list <i>L</i>={<i>J</i><sub>1</sub>,<i>J</i><sub>2</sub>,...,<i>J</i><sub>n</sub>} satisfies <i>p<sub>j</sub></i>∈[1,<i>r</i>](<i>r</i>≥1). Our result improves the best existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.</span> 
</div>
%K 排序问题，平行机，<i>LPT</i>算法，最坏性能比<br>Scheduling Problem
%K Identical Machine
%K <i>LPT</i> Algorithm
%K Worst Performance Ratio
%U http://www.hanspub.org/journal/PaperInformation.aspx?PaperID=31311