﻿ 同类机上工件实时到达在线排序问题 Online Scheduling Problem for Jobs Arriving over Time on Related Machines

Operations Research and Fuzziology
Vol. 09  No. 04 ( 2019 ), Article ID: 32821 , 6 pages
10.12677/ORF.2019.94032

Online Scheduling Problem for Jobs Arriving over Time on Related Machines

Lina Ma1,2, Rongheng Li1*

1Key Laboratory of High Performance Computing and Stochastic Information Processing, College of Mathematics and Statistics, Hunan Normal University, Changsha Hunan

2The First Middle School of Yuanling County, Huaihua Hunan

Received: Oct. 15th, 2019; accepted: Oct. 29th, 2019; published: Nov. 5th, 2019

ABSTRACT

Online scheduling problem for jobs arriving over time is as follow. We are given m related machines ${M}_{1},{M}_{2},\cdots ,{M}_{m}$ with the processing speed of ${s}_{1},{s}_{2},\cdots ,{s}_{m-1},{s}_{m}$ , respectively and a job list $L=\left\{{J}_{1},{J}_{2},\cdots ,{J}_{n}\right\}$ arriving over time. The objective function is to minimize the maximum completion time of all machines. In this paper, LS algorithm is considered for online scheduling problem for jobs arriving over time under the assumption ${s}_{1}={s}_{2}=\cdots ={s}_{m-1}=1$ , ${s}_{m}>1$ . The worst performance ratio of the LS algorithm is given and proved.

Keywords:Scheduling Problem, Related Machine, LS Algorithm, Worst Performance Ratio

1计算与随机数学教育部重点实验室 湖南师范大学数学与统计学院，湖南 长沙

2沅陵县第一中学，湖南 怀化

1. 引言

${J}_{j}\left(j=1,2,\cdots ,n\right)$ 的大小为 ${p}_{j}$，工件 ${J}_{j}$ 安排在机器 ${M}_{i}$ 上加工时所需的时间为 $\frac{{p}_{j}}{{s}_{i}}$，目标函数是使所有

$\frac{1+\sqrt{5}}{2}$$m\ge 3$ 时最坏性能比为 $1+\frac{\sqrt{2m-2}}{2}$，当 ${s}_{1}={s}_{2}=\cdots ={s}_{m-1}=1$ , ${s}_{m}>1$ 时最坏性能比为 $3-\frac{4}{m+1}$ 。Berman等 [4] 得到最坏性能比为 $3+\sqrt{8}\approx 5.828$，并证明了问题的下界为≈4.311。此外，关于机器数m取较小的值时，也有一些结果。例如：当 $m=2$ 时，Epstein等 [5] 证明了LS是最好的在线算法，其最坏性能比为 $\mathrm{min}\left\{\frac{2s+1}{s+1},\frac{s+1}{s}\right\}$，这里的s为加工速度较快的机器与加工速度较慢的机器两者的加工速

2. 符号及LS算法

1) Ui表示在 LS 算法下机器 ${M}_{i}\left(i=1,2,\cdots ,m\right)$ 上面的空闲时间总和。

2) rj和pj分别表示工件Jj的到达时间和工件大小。

3) ${C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$ 表示在OPT算法下机器的最大完工时间。

4) ${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)$ 表示在LS算法下机器的最大完工时间。

5) Hi表示在LS算法下安排最后一个工件Jn之前机器 ${M}_{i}\left(i=1,2,\cdots ,m\right)$ 的完工时间。

6) Fi表示在LS算法下安排完所有的工件后机器 ${M}_{i}\left(i=1,2,\cdots ,m\right)$ 的最后完工时间。

$R\left(m,A\right)=\underset{L}{\mathrm{sup}}\frac{{C}_{\mathrm{max}}^{A}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}$

LS算法：

$\begin{array}{l}\mathrm{min}\left\{\mathrm{max}\left\{{L}_{i},{r}_{j}\right\}+{p}_{j},\mathrm{max}\left\{{L}_{m},{r}_{j}\right\}+\frac{{p}_{j}}{s}|i=1,2,\cdots ,m-1\right\}\\ =\left\{\begin{array}{l}\mathrm{max}\left\{{L}_{k},{r}_{j}\right\}+{p}_{j},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }k (1)

LS算法中每个工件的安排需要找出最早完工的机器，机器台数为m，最多m次可以找出，注意到工件个数为n，所以复杂度为O(mn)。

3. 定理及其证明

${C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)\ge \mathrm{max}\left\{\frac{{\sum }_{j=1}^{n}{p}_{j}}{m+s-1},{r}_{j}+\frac{{p}_{j}}{s}|j=1,2,\cdots ,n\right\}$

$\frac{{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\le \left\{\begin{array}{l}2,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s\le \frac{m-1}{m-2}\\ 1+\frac{m-1}{m+s-1}\mathrm{min}\left\{3,s\right\},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\frac{m-1}{m-2}m-1\end{array}$

$s{H}_{m}+{p}_{n}\ge s{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)$ , ${H}_{i}+{p}_{n}\ge {C}_{\mathrm{max}}^{\text{LS}}\left(L\right)$ , $i=1,2,\cdots ,m-1$

$\begin{array}{l}\left(m+s-1\right){C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\\ \le s{H}_{m}+\text{}{p}_{n}+\left(m-1\right)\underset{i=1}{\overset{m-1}{\sum }}\left({H}_{i}+{p}_{n}\right)\\ =\underset{j=1}{\overset{n}{\sum }}{p}_{n}+\underset{i=1}{\overset{m-1}{\sum }}{U}_{i}+s{U}_{m}+\left(m-1\right){p}_{n}\\ \le \left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\left(m+s-1\right)\left({C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)-\frac{{p}_{n}}{s}\right)+\left(m-1\right){p}_{n}\\ =2\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\frac{s\left(m-1\right)-\left(s+m-1\right)}{s}{p}_{n}\end{array}$

$s\left(m-1\right)\le s+m-1$$\left(m+s-1\right){C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le 2\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$ 即有：

$\frac{{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\le 2$

$s\left(m-1\right)>s+m-1$ 时，由于 ${C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)>\frac{{p}_{n}}{s}$，所以有

$\frac{{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\le \left\{\begin{array}{l}2,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s\le \frac{m-1}{m-2}\\ 1+\frac{s\left(m-1\right)}{m+s-1},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s>\frac{m-1}{m-2}\end{array}$ (2)

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le {H}_{m}+\frac{{p}_{n}}{s}\le {C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le {H}_{m}+\frac{{p}_{n}}{s}\le {C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\frac{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}{s}\le 2{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le 2{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${H}_{i}+{t}^{\prime }\ge {H}_{m}-\frac{SUC\left({t}^{\prime }\right)}{s},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }i=1,2,\cdots ,m-1$

${U}_{m}+\frac{SUC\left({t}^{\prime }\right)+{p}_{n}}{s}\le {C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${H}_{i}+{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)\ge {H}_{i}+{t}^{\prime }\ge {H}_{m}-\frac{SUC\left({t}^{\prime }\right)}{s}={H}_{m}+\frac{{p}_{n}}{s}+{U}_{m}-\frac{s{U}_{m}+SUC\left({t}^{\prime }\right)+{p}_{n}}{s}\ge {C}_{\mathrm{max}}^{\text{LS}}\left(L\right)+{U}_{m}-{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le {H}_{i}-{U}_{m}+2{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)$

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le {H}_{i}+{p}_{n}\le {H}_{i}+{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)\le {H}_{i}-{U}_{m}+2{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right),i=1,2,\cdots ,m-1$

${C}_{\mathrm{max}}^{\text{LS}}\left(L\right)\le {H}_{i}-{U}_{m}+2{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right),i=1,2,\cdots ,m-1$

$\begin{array}{l}\frac{{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}=\frac{s{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)+\left(m-1\right){C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\le \frac{s{H}_{m}+{p}_{n}+{\sum }_{i=1}^{m-1}{H}_{i}+2\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)-\left(m-1\right){U}_{m}}{\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\\ =\frac{\left(s-m+1\right){U}_{m}+{\sum }_{i=1}^{m-1}{U}_{i}+{\sum }_{j=1}^{n}{p}_{n}+2\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}{\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\\ \le \left\{\begin{array}{l}\frac{\left(s-m+1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+2\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}{\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s\ge m-1\\ \frac{\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)+2\left(m-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}{\left(m+s-1\right){C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }sm-1\\ 1+\frac{3\left(m-1\right)}{m+s-1},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s\le m-1\end{array}\end{array}$

4. 小结

$\frac{{C}_{\mathrm{max}}^{\text{LS}}\left(L\right)}{{C}_{\mathrm{max}}^{\text{OPT}}\left(L\right)}\le \left\{\begin{array}{l}2,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }s\le \frac{m-1}{m-2}\\ 1+\frac{m-1}{m+s-1}\mathrm{min}\left\{3,s\right\},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\frac{m-1}{m-2}m-1\end{array}$

Online Scheduling Problem for Jobs Arriving over Time on Related Machines[J]. 运筹与模糊学, 2019, 09(04): 279-284. https://doi.org/10.12677/ORF.2019.94032

1. 1. Gonzalez, T., Ibarra, O.H. and Sahni, S. (1977) Bounds for LPT Scheduling on Uniform Processors. SIAM Journal on Computing, 6, 155-166. https://doi.org/10.1137/0206013

2. 2. Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039

3. 3. Cho, Y. and Sahni, S. (1980) Bounds for List Schedules on Uniform Pro-cessors. SIAM Journal on Computing, 9, 91-103. https://doi.org/10.1137/0209007

4. 4. Berman, P., Chanrikar, M. and Karpinski, M. (2000) Online Load Balancing for Related Machines. Journal of Algorithms Archive, 35, 108-121. https://doi.org/10.1006/jagm.1999.1070

5. 5. Epstein, L., Noga J., Seiden, S., Sgall, J. and Woeginger, G.J. (2001) Randomized Online Scheduling on Two Uniform Machines. Journal of Scheduling, 4, 71-92. https://doi.org/10.1002/jos.60

6. 6. 蔡圣义. 三台同类机在线排序问题一种特殊情形的研究[J]. 系统工程理论与实践, 2006, 26(7): 41-46.

7. 7. Cai, S.Y. and Yang, Q.F. (2012) Online Scheduling on Three Uniform Machines. Discrete Applied Mathematics, 160, 291-302. https://doi.org/10.1016/j.dam.2011.10.001

8. 8. Li, R.H. and Huang, H.C. (2004) On-line Scheduling for Jobs with Arbitrary Release Times. Computing, 73, 79-97. https://doi.org/10.1007/s00607-004-0067-1

9. NOTES

*通讯作者。