Luận án Nghiên cứu một số vấn đề lập lịch trên môi trường tính toán đám mây

nhỏ nhĐt cừa yảu cƯu con là p. R là têp tài nguyản cú
sđn và cú thº thực hiằn song song. Mội tài nguyản rj 2 R cú tốc độ tẵnh toĂn sj và tương
ựng chi phẵ cj để thuả mĂy Êo. Tốc độ sj là số chu kỳ cừa tài nguyản cú thº hoàn thành
trản phỳt. Người dựng trÊ chi phẵ cj để thuả tài nguyản rj trong khoÊng D phỳt liản tục,
D là đơn vị nhỏ nhĐt để thuả.
 Bài toĂn thự nhĐt cú thº mụ tÊ như sau: “Tỡm mởt Ănh xÔ tứ têp yảu cƯu T vào mởt
têp con cừa têp tài nguyản R để tối thiºu tờng thời gian thực hiằn trong khi văn thỏa mÂn
thời hÔn và ngƠn sĂch cừa cĂc yảu cƯu trong T ”. Bài toĂn thự 2: “Tỡm mởt Ănh xÔ tứ têp
yảu cƯu T vào mởt têp con cừa têp tài nguyản R để nhỏ nhĐt toàn bở chi phẵ trong khi
văn thỏa mÂn thời hÔn và ngƠn sĂch cừa cĂc yảu cƯu trong T ”
2.2.2. Mụ hẳnh toĂn học cho bài toĂn
 Luên Ăn mở rởng mụ hẳnh cừa K.H. Kim và K. Kumar, ngoài thời hÔn chỳng ta phÊi
xem x²t ngƠn sĂch cừa cĂc yảu cƯu, đảm bÊo cĂc yảu cƯu được thực hiằn trước thời hÔn và
khụng vượt quĂ ngƠn sĂch cừa nú. Gọi R = fr1; r2; :::; rM g là têp M tài nguyản tẵnh toĂn,
 6
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
cĂc tài nguyản này cú thº thực hiằn song song. Mội tài nguyản rj 2 R là bở ,
trong đú sj là tốc độ tẵnh toĂn tẵnh trản phỳt, cj là chi phẵ để thuả tài nguyản trong
khoÊng thời gian D phỳt. CĂc tài nguyản này là nguồn tẵnh toĂn cho N yảu cƯu độc lêp,
được biºu diạn bởi têp T = ft1; t2; : : : ; tN g, mội yảu cƯu ti 2 T là mởt bở 4 .
 Gọi amin, dmax là thời điểm đến nhỏ nhĐt và thời hÔn lớn nhĐt cừa tĐt cÊ cĂc yảu cƯu.
 Ký hiằu α(j; k; x) để thº hiằn viằc chọn tài nguyản:
 8
 <1 náu tÔi phỳt x, tài nguyản rj được sỷ dụng tứ 1 đến k lƯn.
 α(j; k; x) = (2.1)
 :0 náu tÔi phỳt x, tài nguyản rj khụng được sỷ dụng.
 Tờng chi phẵ cừa cĂc tài nguyản tÔi phỳt thự x (x = amin::dmax) được tẵnh như sau:
 M y
 X X cj
 S (x) = ì α(j; k; x) (2.2)
 cost D
 j=1 k=1
 C
 Trong đú, M là số tài nguyản trong R, y = p với:
 N
 X
 C = wi (2.3)
 i=1
 p = minfsj; j = 1::Mg (2.4)
 Tờng số chu kỳ thực hiằn tÔi phỳt thự x được xĂc định như sau:
 M y
 X X
 Scycle(x) = sj ì α(j; k; x) (2.5)
 j=1 k=1
2.2.3. Mục tiảu tối ưu vã chi phẵ
 Để đạt được mục tiảu nhỏ nhĐt vã chi phẵ thẳ phÊi tẳm cực tiºu tờng chi phẵ:
 d
 Xmax
 Scost(x) ! min (2.6)
 x=amin
Để đạt mục tiảu như cụng thực (2.6) thẳ phÊi thỏa mÂn hai ràng buởc cừa yảu cƯu ti 2 T :
 d
 Xi
 Scost(x) ≤ bi (2.7)
 x=ai
 d
 Xi
 Scycle(x) ≥ wi (2.8)
 x=ai
2.2.4. Mục tiảu tối ưu vã thời gian
 Để đạt được mục tiảu tối ưu vã thời gian thực hiằn cho cĂc yảu cƯu thẳ phÊi tẳm cực
đại tờng số chu kỳ:
 d
 Xmax
 Scycle(x) ! max (2.9)
 x=amin
 Để đạt được mục tiảu trản thẳ phÊi thỏa mÂn hai ràng buởc ở (2.7) và (2.8).
 7
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
2.3. Tối ưu vã kinh tá
 Mội mĂy Êo cừa nhà cung cĐp IaaS được thuả trong D-phỳt và nhà cung cĐp SaaS
phÊi trÊ mởt chi phẵ cố định trong D-phỳt đưủc thuả, náu họ khụng sỷ dụng hát D-phỳt
thẳ họ cũng phÊi trÊ chi phẵ cho toàn bở D-phỳt. Luên Ăn tên dụng khoÊng thời gian cỏn
hiằu lực trong vỏng D-phỳt được thuả cừa yảu cƯu này để thực hiằn cho yảu cƯu khĂc
nhơm đem lÔi lủi nhuên cao nhĐt cho nhà cung cĐp SaaS.
 Gọi Ti là têp cĂc yảu cƯu trong cựng mởt nhà cung cĐp với yảu cƯu ti và gối đầu lản
yảu cƯu ti, cĂc yảu cƯu này cú thº chia s´ cựng 1 mĂy Êo. Ti được xĂc định như sau:
  
 Ti = tljdl ≥ di và al < di (2.10)
 Gọi tiljx là thời gian cỏn hiằu lực để tẵnh toĂn cho yảu cƯu tl sau khi đó thực hiằn xong
yảu cƯu ti trản mĂy Êo vmjx. tiljx được xƠy dựng như sau:
 8
 wi
 >min(D − Uiljx; dl − al) náu al − ai ≥
 > sijx
 wi
 tiljx = D − Uiljx náu al − ai < và dl − ai ≥ D (2.11)
 sijx
 >
 > wi
 :dl − (ai + Uiljx)náu al − ai < và dl − ai < D
 sijx
 wi
Trong đú: Uiljx = + max(al − di; 0) và sijx là tốc độ cừa vmjx được Ănh xÔ vào ti.
 sijx
 Náu x²t trản mởt nhà cung cĐp IaaS thẳ cụng thực (2.11) được xƠy dựng lÔi như sau:
 8
 wi
 >min(D − Uilj; dl − al) náu al − ai ≥
 > sij
 wi
 tilj = D − Uilj náu al − ai < và dl − ai ≥ D (2.12)
 sij
 >
 > wi
 :dl − (ai + Uilj)náu al − ai < và dl − ai < D
 sij
2.4. Thuêt toĂn lêp lịch trản cĂc hằ thống thời gian thực
2.4.1. Thuêt toĂn lêp lịch tối ưu vã thời gian
 CĂc thuêt toĂn này được sỷ dụng để giÊi quyát bài toĂn thự nhĐt.
2.4.1.1. Thuêt toĂn CTO
 CĂc bước cừa Thuêt toĂn CTO được mụ tÊ ở Thuêt toĂn 2.1
 Nhên x²t: mặc dự thuêt toĂn CTO tối ưu vã thời gian, đảm bÊo cĂc yảu cƯu hoàn
thành trước thời hÔn cừa nú, nhưng thuêt toĂn này cỏn mởt số hÔn chá: thuêt toĂn CTO
ch¿ xem x²t số tài nguyản (mĂy Êo) trản mởt nhà cung cĐp, náu x²t trản nhiãu nhà cung
cĐp thẳ độ phực tÔp cừa thuêt toĂn s³ lớn; cĂc yảu cƯu luụn hoàn thành trước thời hÔn
nhưng cú thº khụng thỏa mÂn ngƠn sĂch cừa nú; thời gian thuả tài nguyản là D phỳt
nhưng cú thº cú nhiãu yảu cƯu khụng sỷ dụng hát D phỳt.
2.4.1.2. Thuêt toĂn MINC
 Để khưc phục cĂc hÔn chá cừa thuêt toĂn CTO, chỳng tụi xƠy dựng thuêt toĂn MINC
nhơm tên dụng khoÊng thời gian cỏn hiằu lực giỳa cĂc yảu cƯu với mục tiảu tối ưu vã chi
 8
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 Thuêt toĂn 2.1: CTO
 Đầu vào:
 • T = ft1; t2; : : : ; tN g, 8ti 2 T là mởt bở 4 ;
 • R = fr1; r2; :::; rM g, 8rj 2 R là bở 
 Đầu ra : MÊng kát quÊ Result chựa số lưủng cĂc tài nguyản cho mội yảu cƯu;
 Phương phĂp:
 1 Chọn ngưỡng ρ 2 N : 1 ≤ ρ ≤ p, p được xĂc định như cụng thực (2.4);
 2 Sưp xáp cĂc tài nguyản theo thự tự giÊm dƯn cừa tốc độ;
 3 Dựa vào ngưỡng ρ để nhúm cĂc tài nguyản theo tốc độ;
 4 G :=số nhúm tài nguyản nhúm đưủc;
 5 RG := fg1; g2; :::; gGg; gl 2 G chựa cĂc tài nguyản cừa nhúm;
 6 Trản mội nhúm, sưp xáp cĂc tài nguyản theo thự tự tông dƯn cừa chi phẵ;
 7 Result:= CalculateParallel(RG,T );
 Function CalculateParallel(RG,T )
 1 TÔo G luồng (thread) chÔy đồng thời: TH := fth1; th2; :::; thGg; thj 2 TH tẳm kiám
 tài nguyản tương ựng trản nhúm gj 2 RG;
 2 foreach thj 2 TH do
 3 foreach ti 2 T do
  wi 
 4 Tẵnh số lượng cừa tài nguyản đầu tiản r1 2 gj cho ti: sli :=  ;
 (di − ai) ì s1 
 5 if wi > (di − ai) ì s1 và jgjj = 1 then
 6 sli := sli + 1;
 7 else
 8 if wi > (di − ai) ì s1 then
 9 Tẵnh số lượng cĂc tài nguyản cỏn lÔi cừa nhúm gj cho ti ;
10 Result[j; i] := Số lượng và tản tài nguyản trong gj được thực hiằn cho ti;
phẵ. Thuêt toĂn MINC bao gồm cĂc bước được mụ tÊ ở Thuêt toĂn 2.2.
2.4.1.3. PhƠn tẵch thuêt toĂn CTO và MINC
 • Đầu vào cừa thuêt toĂn CTO và MINC: têp R được xĂc định vẳ tÔi thời điểm lêp
 lịch dựa vào thụng tin cừa hằ thống ta cú thº xĂc định được số lượng tài nguyản
 trản trung tƠm dỳ liằu. Sự hẳnh thành cừa têp T và UST trong thuêt toĂn CTO
 và MINC được giới hÔn vẳ cĂc yảu cƯu được lêp lịch theo lụ và theo mởt chu kỳ.
 • Đối với thuêt toĂn CTO: sau khi thực hiằn tứ cƠu lằnh 1 đán cƠu lằnh 6, ta cú G
 nhúm tài nguyản độc lêp, cĂc tài nguyản đầu tiản cừa mội nhúm s³ cú chi phẵ thĐp
 9
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 Thuêt toĂn 2.2: MINC
 Đầu vào:
 • UST := T ; /* têp cĂc yảu cƯu chưa lêp lịch */
 • MÊng Result ; /* MÊng kát quÊ là đầu ra cừa thuêt toĂn CTO. */
 Đầu ra : ST là lịch trẳnh để Ănh xÔ cĂc yảu cƯu vào cĂc tài nguyản;
 Phương phĂp:
 1 ST := ;;
 2 if tẳm thĐy ti 2 UST thỏa mÂn thời hÔn và ngƠn sĂch trong Result then
 3 k:= vị trẵ cừa dỏng trản Result tẳm thĐy ti;
 4 P USH(ti); UST := UST n ftig; ST := ST [ fti ! Result [k; i]g;
 5 while (UST 6= ;) do
 6 ti := P OP () ; /* LĐy ti tứ ngôn xáp */
  
 7 Tẳm Ti := tljdl ≥ di và al < di ;
 8 Tẵnh tilj trản tài nguyản cuối cựng được Ănh xÔ bởi yảu cƯu ti như cụng thực
 8 wi
 > min (D − Uilj; dl − al) náu al − ai ≥
 sij
 wi
 (2.12): tilj := D − Uilj náu al − ai < s và dl − ai ≥ D ;
 > ij
 > wi
 : dl − (ai + Uil) náu al − ai < và dl − ai < D
 sijx
 9 Dựa trản tilj tẵnh đưủc trong Ti để cêp nhêt lÔi khối lượng cho cĂc yảu cƯu
 trong Ti và tẳm ra yảu cƯu tl 2 Ti cú khoÊng thời gian gối đầu lớn nhĐt vứa
 thỏa mÂn thời hÔn và ngƠn sĂch;
10 if tẳm thĐy tl then
11 P USH(tl); UST := UST n ftlg;
12 ST := ST [ ftl ! Result [k; l]g;
13 else
14 Lặp lÔi bước 2 để tẳm yảu cƯu tiáp theo;
15 else
16 Thụng bĂo cĂc yảu cƯu ti 2 UST bị tứ chối;
 nhĐt so với cĂc tài nguyản cỏn lÔi cừa nhúm và cĂc tài nguyản cừa nhúm đầu tiản
 s³ cú tốc độ lớn nhĐt. Vẳ G nhúm tài nguyản này độc lêp nản ta cú thº Ăp dụng mụ
 hẳnh lêp trẳnh chia x´ bở nhớ để tÔo ra G luồng chÔy đồng thời, mội luồng s³ tẵnh
 toĂn tài nguyản trản mội nhúm tương ựng. Trản mội luồng s³ ưu tiản Ănh xÔ yảu
 cƯu vào tài nguyản đầu tiản cừa mội nhúm, điều này s³ làm giÊm chi phẵ cho cÊ hằ
 thống. Vẳ thuêt toĂn sỷ dụng G luồng chÔy đồng thời nản s³ tối ưu thời gian đưa
 ra cĂc lịch trẳnh cừa thuêt toĂn.
 • Thời gian thuả tài nguyản là D-phỳt, do đú cú thº mởt yảu cƯu nào đú hoàn thành
 10
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 cụng viằc cừa mẳnh với thời gian ẵt hơn D-phỳt nhưng phÊi trÊ chi phẵ trong vỏng
 D-phỳt. Thuêt toĂn MINC tên dụng khoÊng thời gian cỏn hiằu lực này để thực
 hiằn cho yảu cƯu tiáp theo, điều này dăn đến chi phẵ thực hiằn cho cÊ hằ thống giÊm
 xuống và đem lÔi lủi ẵch cho nhà cung cĐp SaaS.
 M M
 • Độ phực tÔp cừa thuêt toĂn CTO là O(max(M ì log2 ; G; N ì M)). Náu N > log2
 thẳ đở phực tÔp cừa CTO là O(N ì M), ngược lÔi thẳ độ phực tÔp cừa CTO là
 M 2
 O(M ì log2 ). Độ phực tÔp cừa thuêt toĂn MINC là O(max(N ;N ì G)), trường
 hủp xÊy ra nhiãu nhĐt là N > G thẳ độ phực tÔp cừa MINC là O(N 2), ngược lÔi
 thẳ độ phực tÔp cừa MINC là O(N ì G).
2.4.1.4. Mụ phỏng và đỏnh giĂ thuêt toĂn
 CĂc thuêt toĂn được cài đặt mụ phỏng bơng cụng cụ CloudSim 2.0, sỷ dụng 1 Dat-
aCenter, 2 host, 50 mĂy Êo, số yảu cƯu thay đổi tứ 100 đến 250. Lịch trẳnh đưa ra cừa
thuêt toĂn CTO và MINC được so sĂnh với thuêt toĂn tham lam EDF .
(a) So sĂnh tờng thời gian cừa 3 thuêt toĂn khi thay(b) So sĂnh tờng chi phẵ cừa 3 thuêt toĂn khi thay
đổi số yảu cƯu đổi số yảu cƯu
(c) So sĂnh tờng thời gian thực hiằn cừa 3 thuêt toĂn(d) So sĂnh tờng chi phẵ cừa 3 thuêt toĂn khi thay
khi thay đổi ρ đổi ρ
 Hẳnh 2.1: So sĂnh tờng chi phẵ và thời gian khi thay đổi số yảu cƯu và ngưỡng
 PhƠn tẵch tờng thời gian và chi phẵ thực hiằn khi thay đời số yảu cƯu
 11
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 Hẳnh 2.1(a) và (b) trẳnh bày tờng thời gian thực hiằn và tờng chi phẵ cừa cĂc thuêt
toĂn khi ρ = 5, D = 60, sỷ dụng 50 mĂy Êo và cĂc yảu cƯu thay đổi tứ 100 đến 250.
 PhƠn tẵch tờng thời gian và tờng chi phẵ khi thay đổi số ngưỡng ρ
Chỳng tụi thay đổi ngưỡng ρ tứ 1 đến 5, D = 60, sỷ dụng 250 yảu cƯu và 50 mĂy Êo, kát
quÊ cừa cĂc thuêt toĂn được thº hiằn ở Hẳnh 2.1(c) và Hẳnh 2.1(d).
2.4.2. Thuêt toĂn lêp lịch tối ưu vã chi phẵ
2.4.2.1. Thuêt toĂn TCO
 CĂc bước cừa Thuêt toĂn TCO được mụ tÊ trong thuêt toĂn 2.3.
 Thuêt toĂn 2.3: TCO
 Đầu vào:
 • T = ft1; t2; : : : ; tN g, 8ti 2 T là mởt bở 4 ;
 • R = fr1; r2; :::; rM g, 8rj 2 R là bở 
 Đầu ra : MÊng Result để xĂc định số lượng cĂc tài nguyản cho mội yảu cƯu;
 Phương phĂp:
 1 Chọn ngưỡng ρ 2 (0; 1] ;
 2 Sưp xáp cĂc tài nguyản theo thự tự tông dƯn cừa chi phẵ;
 3 Dựa vào ngưỡng ρ để nhúm cĂc tài nguyản theo chi phẵ;
 4 G := số nhúm tài nguyản nhúm đưủc;
 5 RG := fg1; g2; :::; gGg; gl 2 G chựa cĂc tài nguyản cừa nhúm;
 6 Trản mội nhúm, sưp sáp cĂc tài nguyản theo thự tự giÊm dƯn cừa tốc độ;
 7 Result:= CalculateParallel(RG, T );
2.4.2.2. Mụ phỏng và đỏnh giĂ thuêt toĂn
 Giống như thuêt toĂn CTO, thuêt toĂn TCO được cài đặt mụ phỏng bơng cụng cụ
CloudSim 2.0, sỷ dụng 1 DataCenter, 2 host, 50 mĂy Êo, số yảu cƯu thay đổi tứ 100 đến
250. Lịch trẳnh đưa ra cừa thuêt toĂn TCO và MINC được so sĂnh với thuêt toĂn tham
lam EDF .
 PhƠn tẵch tờng chi phẵ và thời gian thực hiằn khi thay đời số yảu cƯu
 Hẳnh 2.2 (a) và (b) trẳnh bày tờng chi phẵ và tờng thời gian thực hiằn cừa 3 thuêt toĂn
TCO, MINC và EDF khi ρ=0.5, D=60, sỷ dụng 50 mĂy Êo và cĂc yảu cƯu thay đổi tứ
100 đến 250.
 PhƠn tẵch tờng chi phẵ và tờng thời gian khi thay đổi ngưỡng ρ
 Hẳnh 2.2 (c) và (d) trẳnh bày kát quÊ cừa cĂc thuêt toĂn khi thay đổi ngưỡng ρ tứ 0.1
đến 0.5, D = 60, sỷ dụng 200 yảu cƯu và 50 mĂy Êo.
 12
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
(a) So sĂnh tờng chi phẵ cừa 3 thuêt toĂn khi thay(b) So sĂnh tờng thời gian cừa 3 thuêt toĂn khi thay
đổi số yảu cƯu đổi số yảu cƯu
(c) So sĂnh tờng chi phẵ cừa 3 thuêt toĂn khi thay(d) So sĂnh tờng thời gian thực hiằn cừa 3 thuêt toĂn
đổi ρ khi thay đổi ρ
 Hẳnh 2.2: So sĂnh tờng chi phẵ và thời gian khi thay đổi số yảu cƯu và ngưỡng
2.5. Tiºu kát Chương 2
 Chương này têp trung mụ tÊ và xƠy dựng mụ hẳnh cho bài toĂn lêp lịch thời gian thực
trong cĂc ựng dụng song song. Kát hủp với xỷ lý song song và phƠn nhúm, luên Ăn đưa
ra 3 thuêt toĂn CT O; MINC và TCO để giÊi quyát 2 bài toĂn:
 • Bài toĂn lêp lịch trản cĂc hằ thống thời gian thực theo hướng tối ưu vã thời gian.
 • Bài toĂn lêp lịch trản cĂc hằ thống thời gian thực theo hướng tối ưu vã chi phẵ.
 13
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
Chương 3.
 LẬP LỊCH CặNG VIỆC THEO HƯỚNG TẩI ƯU
 ĐA MỤC TIấU TRONG TÍNH TOÁN ĐÁM MÂY
3.1. Mụ hẳnh lêp lịch theo hướng tối ưu đa mục tiảu
 Trong TTĐM, mội tĂc nhƠn đều cú yảu cƯu dịch vụ hoặc cung cĐp dịch vụ với cĂc
mục tiảu khĂc nhau như nhà cung cĐp SaaS cƯn đem lÔi lủi ẵch lớn nhĐt cho mẳnh; nhà
cung cĐp PaaS cƯn tên dụng tài nguyản mởt cĂch hiằu quÊ, v.v.
3.1.1. Mụ hẳnh người dựng
 Luên Ăn mở rởng mụ hẳnh người dựng cừa R. Buyya bơng cĂch phĂt triºn thảm cĂc
thuởc tẵnh như thời hÔn, ngƠn sĂch, v.v. X²t trản N yảu cƯu dịch vụ T = ft1; t2; : : : ; tN g,
mội yảu cƯu ti 2 T là mởt bở 7 , trong đú: ai: thời điểm đến
cừa yảu cƯu; thời hÔn di ; ngƠn sĂch bi; t¿ lằ lÂi suĐt phÔt αi; khối lượng cụng viằc wi;
kẵch cỡ file đầu vào và đầu ra cừa yảu cƯu: ini và outi
3.1.2. Mụ hẳnh nhà cung cĐp IaaS
 Xem x²t trản Y nhà cung cĐp IaaS: X = f1; 2; ::; Y g. Mội nhà cung cĐp x 2 X
cung cĐp Mx mĂy Êo cho cĂc nhà cung cĐp SaaS, được biºu diạn bởi têp VMx =
fvm1x; vm2x; : : : ; vmMxxg. Theo mụ hẳnh IaaS cừa R. Buyya, mội mĂy Êo vmjx 2 VMx
là mởt bở 5 ; trong đú: thời gian khởi tÔo tjx; giĂ pjx; tốc độ
xỷ lý sjx; giĂ tẵnh theo dung lượng truyãn dtpjx; tốc độ truyãn dtsjx
3.1.3. Mụ hẳnh nhà cung cĐp PaaS
 Luên Ăn đề xuĐt mụ hẳnh nhà cung cĐp PaaS là bở ba: và
. Trong đú, R là têp cĂc nhà cung cĐp IaaS độc lêp và tài nguyản
trong cĂc nhà cung cĐp cú thº thực hiằn song song, npmtn là têp N yảu cƯu độc lêp
khụng theo thự tự ưu tiản (non-preemptive). Mục đớch cừa chỳng tụi là lêp lịch cho cĂc
yảu cƯu người dựng trản têp tài nguyản cừa cĂc nhà cung cĐp IaaS theo hướng tối ưu vã
chi phẵ và tối ưu vã thời gian nghĩa là phÊi tẳm ra Cmin và Tmin.
 Gọi Cijx là chi phẵ để xỷ lý yảu cƯu ti 2 T trản mĂy Êo vmjx 2 VMx. Theo mụ
hẳnh cừa người dựng và mụ hẳnh cừa nhà cung cĐp IaaS, chi phẵ Cijx được tẵnh như sau:
Cijx = CPijx + CTDijx + CIijx + CRijx, trong đú:
 wi
 CPijx = pjx ì (3.1)
 sjx
 ini + outi
 CTDijx = dtpjx ì (3.2)
 dtsjx
 CIijx = tijx ì pijx (3.3)
 14
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 CRijx = αi ì βijx (3.4)
 Gọi Tijx là thời gian để xỷ lý yảu cƯu ti 2 T trản mĂy Êo vmjx 2 VMx:
 Tijx = CTijx + DTijx + TIijx + βijx (3.5)
 Trong đú:
 wi
 CTijx = (3.6)
 sjx
 ini + outi
 DTijx = (3.7)
 dtsjx
TIijx: thời gian khởi tÔo mĂy Êo đó cú. βijx: thời gian vượt thời hÔn.
 Hàm mục tiảu vã chi phẵ cho yảu cƯu ti 2 T được biºu diạn như sau:
 fcost(ti) = min fCijxg (3.8)
 x=1::Y; j=1::Mx
 và mục tiảu cừa nhà cung cĐp SaaS là tẳm cực đại cừa tờng lủi nhuên:
 N
 X
 (bi − fcost(ti)) ! max (3.9)
 i=1
và thỏa mÂn 2 ràng buởc cho yảu cƯu ti:
 Cijx < bi (3.10)
 Tijx ≤ di + βijx (3.11)
 Hàm mục tiảu vã thời gian cho yảu cƯu ti 2 T được biºu diạn như sau:
 ftime(ti) = min fTijxg (3.12)
 x=1::Y; j=1::Mx
 và mục tiảu cừa người dựng là tẳm cực tiºu tờng thời gian thực hiằn:
 N
 X
 (ftime(ti)) ! min (3.13)
 i=1
và thỏa mÂn 2 ràng buởc ở cụng thực (3.10) và (3.11).
3.2. XƠy dựng bài toĂn theo hướng tối ưu đa mục tiảu
 Trong phƯn này chỳng tụi nghiản cựu cĂc phương phĂp heuristic ACO và P SO để xƠy
dựng bài toĂn nhơm đạt được mục tiảu cho người dựng và nhà cung cĐp SaaS.
3.2.1. Tối ưu húa đàn kián (ACO)
 Thuêt toĂn ACO dựa trản hành vi cừa đàn kián trong tự nhiản được Marco Dorigo
giới thiằu, để Ăp dụng thuêt toĂn ACO vào bài toĂn cụ thº, luên Ăn xƠy dựng cĂc thụng
tin: hàm cực tiºu F , thụng tin heuristic η, cêp nhêt lÔi mựi và xĂc suĐt P như sau:
 Với mục tiảu tối ưu vã chi phẵ, hàm cực tiºu F và thụng tin heuristic để yảu cƯu ti 2 T
tẳm ra mĂy Êo vmx 2 VMx được xĂc định như sau:
 F (ti) = min fCijxg (3.14)
 x=1::Y; j=1::Mx
 15
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 1
 ηijx = (3.15)
 Cijx
 Với mục tiảu tối ưu vã thời gian, hàm cực tiºu F và ηijx được xĂc định như sau:
 F (ti) = min fTijxg (3.16)
 x=1::Y; j=1::Mx
 1
 ηijx = (3.17)
 Tijx
Cêp nhêt lÔi mựi để lÔi khi kián đi qua:
 τijx = (1 − ρ)τijx + ∆τijx (3.18)
XĂc suĐt để yảu cƯu ti 2 T chọn mĂy Êo vmjx 2 VMx:
 τijxηijx
 Pijx = (3.19)
 PY PMx
 x=1 j=1 τijxηijx
Với mục tiảu tối ưu vã chi phẵ, xĂc suĐt để ti 2 T chọn vmjx 2 VMx được tẵnh như sau:
  1−ρ  1
 (1 − ρ)τijx +
 F (ti) Cijx
 Pijx =   (3.20)
 PY PMx 1−ρ 1
 (1 − ρ)τijx +
 x=1 j=1 F (ti) Cijx
Với mục tiảu tối ưu vã thời gian, xĂc suĐt để ti 2 T chọn vmjx 2 VMx:
  1−ρ  1
 (1 − ρ)τijx +
 F (ti) Tijx
 Pijx =   (3.21)
 PY PMx 1−ρ 1
 (1 − ρ)τijx +
 x=1 j=1 F (ti) Tijx
3.2.2. Tối ưu húa bƯy đàn (P SO)
 Thuêt toĂn P SO dựa trản kinh nghiằm cừa bƯy đàn được đề xuĐt bởi Eberhart và
Kennedy. Để Ăp dụng thuêt toĂn P SO vào bài toĂn cụ thº, luên Ăn xƠy dựng cĂc thụng
tin: vị trẵ, vên tốc, hàm thẵch nghi, vị trẵ tối ưu cục bở cừa tứng cĂ thº và vị trẵ tối ưu
toàn cục cừa cÊ bƯy đàn như sau:
M.Clerc đó đưa ra cụng thực để cêp nhêt lÔi vị trẵ và vên tốc sau mội thá hằ như sau:
 j+1  j j j 

 vx = K !vx + c1z1(P bestx − posx) + c2z2(Gbest − posx) (3.22)
 j+1 j j+1
 posx = posx + vx (3.23)
 j j+1
Trong đú: K là hằ số hởi tụ, posx: vị trẵ hiằn tÔi cừa cĂ thº thự x tÔi chiãu j; posx : vị
trẵ cừa cĂ thº x tÔi chiãu j + 1; c1,c2: hằ số gia tốc; z1,z2: là số ngău nhiản giỳa 0 và 1;
 j
vx: vên tốc cừa cĂ thº x tÔi chiãu j; P bestx: vị trẵ cục bở tốt nhĐt cừa cĂ thº x; Gbest: vị
trẵ tốt nhĐt toàn cục cừa toàn bở bƯy đàn.
 Hàm thẵch nghi vã chi phẵ để cĂ thº x chọn mĂy Êo vmjx 2 VMx cho yảu cƯu ti 2 T :
 j 1
 Fcost(posix) = (3.24)
 Cijx
 Vị trẵ tối ưu cục bở vã chi phẵ cừa cĂ thº x tÔi chiãu j + 1 cho ti được xĂc định:
 16
 Nghiản cựu mởt số thuêt toĂn lêp lịch trản mụi trường tẵnh toĂn đĂm mƠy
 ( j+1 j+1 j
 j+1 pbix náu Fcost(posix ) ≥ Fcost(posix) và Cijx ≤ bi và Tijx ≤ di + βijx
 pbix = j
 pbix ngược lÔi
 (3.25)
 Vị trẵ tối ưu cục bở (P bestx) được xĂc định:
 j
 P bestx = max fpbixg (3.26)
 x=1::Y; j=1::Mx
 Vị trẵ tối ưu toàn cục cừa cÊ đàn (Gbest) xĂc định như sau:
 Gbest = max fP bestxg (3.27)
 x=1::Y
3.3. Thuêt toĂn lêp lịch tối ưu đa mục tiảu dựa trản ACO
3.3.1. PhĂt biºu bài toĂn
 Ứng dụng bao gồm N yảu cƯu dịch vụ, được biºu diạn bởi têp T = ft1; t2; : : : ; tN g,
mội yảu cƯu ti 2 T là mởt bở 7 được gỷi lản nhà cung cĐp
SaaS bao gồm cĂc thuởc tẵnh và cĂc ràng buởc QoS như thº hiằn ở phƯn 3.1.1. Nhà cung
cĐp SaaS thuả cĂc tài nguyản tứ Y nhà cung cĐp IaaS. Mội nhà cung cĐp x (x = 1::Y )
cung cĐp Mx mĂy Êo, mội mĂy Êo vmjx 2 VMx là mởt bở 5 
như thº hiằn ở phƯn 3.1.2. Khi nhên được têp cĂc yảu cƯu cừa người dựng, nhà cung cĐp
PaaS tián hành tẵnh toĂn chi phẵ và thời gian thực hiằn như mụ hẳnh ở phƯn 3.1.3. Tứ
đú, ra quyát định tứ chối hay chĐp nhên yảu cƯu người dựng. Náu yảu cƯu nào được chĐp
nhên thẳ bở lêp lịch s³ Ănh xÔ vào tài n