Geodesic
A parametric scheme for online uniform-machine scheduling to minimize the makespan
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2015), pp. 102-109 
Alexandre Dolgui; Vladimir Kotov; Alain Quilliot. A parametric scheme for online uniform-machine scheduling to minimize the makespan. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2015), pp. 102-109. http://geodesic.mathdoc.fr/item/BASM_2015_3_a7/
@article{BASM_2015_3_a7,
     author = {Alexandre Dolgui and Vladimir Kotov and Alain Quilliot},
     title = {A parametric scheme for online uniform-machine scheduling to minimize the makespan},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {102--109},
     year = {2015},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASM_2015_3_a7/}
}
TY  - JOUR
AU  - Alexandre Dolgui
AU  - Vladimir Kotov
AU  - Alain Quilliot
TI  - A parametric scheme for online uniform-machine scheduling to minimize the makespan
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2015
SP  - 102
EP  - 109
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/BASM_2015_3_a7/
LA  - en
ID  - BASM_2015_3_a7
ER  - 
%0 Journal Article
%A Alexandre Dolgui
%A Vladimir Kotov
%A Alain Quilliot
%T A parametric scheme for online uniform-machine scheduling to minimize the makespan
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2015
%P 102-109
%N 3
%U http://geodesic.mathdoc.fr/item/BASM_2015_3_a7/
%G en
%F BASM_2015_3_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we consider the Online Uniform Machine Scheduling problem in the case when speed $s_i=1$ for $i=n-k+1,\dots,n$ and $S_i=s$, $1\leq s\leq2$ for $i=1,\dots,k$, where $k$ is a constant, and we propose a parametric scheme with an asymptotic worst-case behavior (when $m$ tends to infinity).

[1] Cho Y., Sahni S., “Bounds for list schedules on uniform processors”, SIAM Journal on Computing, 9 (1980), 91–103 | DOI | MR | Zbl

[2] Graham R. L., “Bounds on multiprocessing timing anomalies”, SIAM Journal on Applied Mathematics, 17 (1969), 263–269 | MR

[3] Li R., Shi L., “An on-line algorithm for some uniform processor scheduling”, SIAM Journal on Computing, 27 (1998), 414–422 | DOI | MR | Zbl

[4] Cheng T. C. E., Ng C. T., Kotov Vladimir, “A new algorithm for online uniform-machine scheduling to minimize the makespan”, Information Processing Letters, 99 (2006), 102–105 | DOI | MR | Zbl

[5] Liu Ming, Xu Yinfeng, Chu Chengbin, Zheng Feifeng, “Online scheduling on two uniform machines to minimize the makespan”, Theoretical Computer Science, 410:21–23 (2009), 2099–2109 | DOI | MR | Zbl

[6] Angelelli E., Speranza Maria Grazia, Tuza Z., “Semi-online scheduling on two uniform processors”, Theoretical Computer Science, 393 (2008), 211–219 | DOI | MR | Zbl

[7] Wen J., Du D., “Preemptive on-line scheduling for two uniform processors”, Operations Research Letters, 23 (1998), 113–116 | DOI | MR | Zbl

[8] Kellerer H., Kotov V., “An efficient algorithm for bin stretching”, Operations Research Letters, 41:4 (2013), 343–346 | DOI | MR | Zbl

[9] Kellerer H., Kotov V., Gabay M., “An efficient algorithm for semi-online multiprocessor scheduling with given total processing time”, Journal of Scheduling, 18 (2015), 623–630 | DOI | MR | Zbl