A parametric scheme for online uniform-machine scheduling to minimize the makespan

Alexandre Dolgui; Vladimir Kotov; Alain Quilliot

Geodesic

Parcourir par

A parametric scheme for online uniform-machine scheduling to minimize the makespan

Alexandre Dolgui ; Vladimir Kotov ; Alain Quilliot

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2015), pp. 102-109.

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

Résumé

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 \leq 2

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).

Export
Comment citer

@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},
     publisher = {mathdoc},
     number = {3},
     year = {2015},
     language = {en},
     url = {https://geodesic-test.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
PB  - mathdoc
UR  - https://geodesic-test.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
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/BASM_2015_3_a7/
%G en
%F BASM_2015_3_a7

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. https://geodesic-test.mathdoc.fr/item/BASM_2015_3_a7/

Bibliographie
Cité par

[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