Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
V
o
l.
6, N
o
. 5
,
O
c
tob
e
r
201
6, p
p
. 2
291
~229
9
I
S
SN
: 208
8-8
7
0
8
,
D
O
I
:
10.115
91
/ij
ece.v6
i
5.1
064
0
2
291
Jo
urn
a
l
h
o
me
pa
ge
: h
ttp
://iaesjo
u
r
na
l.com/
o
n
lin
e/ind
e
x.ph
p
/
IJECE
ENPP: Extended Non-preempti
ve PP-aware Scheduling for
Real-time Cloud Services
Fereshte
h
Hos
e
ini
1
,
M
o
st
af
a Gho
b
aei
Ar
an
i
1
, Alirez
a Taghiz
adeh
2
1
Departm
e
nt
of
Com
puter Engin
eering
,
M
a
h
a
ll
at
Branch,
Is
lam
i
c
Azad Unive
r
s
i
t
y
, M
a
ha
ll
at,
Iran
2
Departm
e
nt
of
Com
puter Engin
eering
,
P
a
r
a
nd B
r
anch,
Is
lam
i
c
A
zad Univ
ers
i
t
y
,
Tehran
, Ir
an
Article Info
A
B
STRAC
T
Article histo
r
y:
Received
Mar 23, 2016
Rev
i
sed
Ju
l 6
,
2
016
Accepte
d
J
u
l 24, 2016
B
y
incr
eas
ing t
h
e
us
e
of clou
d
s
e
rv
ices and
the number of
requests to
processing tasks with minimum
time and
cos
t
s
,
the res
ourc
e
all
o
cat
ion an
d
sc
he
dul
i
n
g,
e
s
pec
i
al
ly
i
n
re
al
-time
a
ppl
i
c
a
t
i
ons be
c
o
me
more
c
h
a
l
l
e
ngi
ng.
The problem of resource sc
h
e
duling, is on
e of th
e most important
scheduling
problems in th
e area of
NP-hard probl
ems. In
this pap
e
r, we
propose an
efficient algor
ithm is proposed to sc
hedu
le r
e
al-time
cloud s
e
rvices b
y
considering the resource constraints.
Th
e sim
u
la
tion resul
t
s show that th
e
proposed algor
ithm shorten the
processi
ng time of tasks
and d
ecrease
the
number of canceled
tasks.
Keyword:
C
l
ou
d c
o
m
put
i
n
g
Non
-
ex
cl
u
s
iv
eo
n
lin
e algo
rithm
s
Real-tim
e scheduling
Real-tim
e syste
m
s
Copyright ©
201
6 Institut
e
o
f
Ad
vanced
Engin
eer
ing and S
c
i
e
nce.
All rights re
se
rve
d
.
Co
rresp
ond
i
ng
Autho
r
:
Feresh
teh
Ho
sein
i,
Depa
rt
m
e
nt
of
C
o
m
put
er E
ngi
neeri
n
g
,
Mahallat
Branch, Islam
i
c
Azad Uni
v
ersity,
Mah
a
llat, Iran
.
Em
a
il: feresh
teh
.
h
o
s
sin
i
@g
mail.co
m
1.
INTRODUCTION
The wo
rl
d of
c
o
m
put
i
ng has chan
ge
d dram
at
i
cal
l
y
s
i
nce the appea
r
ance
of
Inte
rnet.
The com
puti
ng
on a singleprocessor has
given its place to parallel com
puting a
n
d final
l
y thedistribut
edcom
puting,
and i
n
part
i
c
ul
a
r
, t
h
e
cl
ou
d c
o
m
put
i
n
g
.
T
h
e cl
ou
d
com
put
i
n
g
i
s
a
ne
w
ge
nerat
i
o
n
of
dat
a
cent
e
rs
wi
t
h
vi
rt
ua
l
i
zed
nodes ha
ving a
set
of resources
th
at are
provi
ded
dynam
i
cally and acco
rdi
ng t
ouse
r
’s
dem
a
nd. T
h
e
cloud
co
m
p
u
tin
g
is
a set o
f
app
licatio
n
s
, system h
a
rdw
a
r
e
and so
f
t
w
a
r
e
pr
ovid
e
d
as
serv
ices [
1
]-[3
]. Th
e cloud
p
r
ov
id
ers sh
ould
gu
ar
an
tee
off
e
r
i
ng
t
h
ese se
rvices as
re
ques
t
ed.
Th
e cloud
com
p
u
tin
g
techno
log
y
pr
ov
id
es th
e serv
ices
in three
form
s of
softwa
re
as a service
(SaaS),
platform as a servi
ce
(PaaS) and infrastructures a s
e
rvice (IaaS
) t
o
the
users. T
h
e IaaS layer
provi
des
th
e v
i
rt
u
a
l in
frastru
c
tu
re in
clu
d
i
ng
t
h
e pro
cesso
r, m
e
mo
ry an
d
n
e
two
r
k
to
supp
ort ex
ecu
tion
variou
s
o
p
e
rating
syste
m
s. Th
e PaaS layer prov
i
d
es th
e trad
ition
a
l serv
ices su
ch as
o
p
e
ratin
g system
s u
s
in
g
t
h
e
reso
u
r
ces p
r
o
v
i
ded by
Iaa
S
.
The SaaS l
a
y
e
r
pr
ovi
des t
h
e a
ppl
i
cat
i
o
n pr
o
g
r
am
whi
c
h t
h
e end
-
users ca
n
wri
t
e
,
d
e
v
e
l
o
p, an
d ex
ecu
te
pr
og
r
a
m
s
in
th
e clo
ud env
i
ro
n
m
en
t [4
].
The cl
o
u
d
co
m
put
i
ng as di
s
t
ri
but
e
d
com
put
i
ng i
s
c
o
m
p
o
s
ed
of a m
a
ny
reso
u
r
cesan
d
r
e
que
st
s wi
t
h
a
purpose
to s
h
a
r
e re
source
s as
services
on the internet
platform
. The
res
o
urces
such
as
me
m
o
ry and proces
sor
are ex
pensi
v
e and t
h
e
opt
i
m
um
use of t
h
em
i
s
consi
d
er
ed
as an i
n
fi
ni
t
e
chal
l
e
nge
. He
nc
e, t
h
e sche
dul
i
ng
of
th
e task
s in th
e clo
u
d
co
m
p
u
t
i
n
g
is a
v
e
ry imp
o
rtan
t issu
e wh
ich
attem
p
ts t
o
d
e
term
in
e an
o
p
tim
u
m
resou
r
ce
allocation [5]. The services
prov
id
ed
in
th
e clo
u
d
en
vironment are essentially based on real-tim
e software
’s.
No
t
p
r
ov
id
ing
th
e req
u
i
red
serv
ices i
n
th
e sp
ecified
tim
e, it
m
i
g
h
t
h
a
v
e
n
o
d
i
re con
s
equ
e
n
c
es bu
t
u
ltimatel
y
lead
s to d
i
ssati
sfactio
n of
th
e
cu
sto
m
er
s [6
],
[7
].
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 5
,
O
c
tob
e
r
20
16
:
229
1
–
22
99
2
292
In
th
is p
a
p
e
r after ev
alu
a
ting th
e p
r
ob
lem
s
o
f
th
e ex
isting alg
o
r
ith
m
s
, it
isatte
m
p
ted
t
o
p
r
ov
id
e a
so
lu
tion
u
s
ing
an
im
p
r
ov
ednon
-
e
x
c
lu
si
v
e
on
l
i
n
e
sch
e
du
ling alg
o
r
ith
m
.
Th
e exp
e
r
i
m
e
n
t
al r
e
su
lts sho
w
that th
e
pr
o
pose
d
m
e
tho
d
has
bet
t
e
r
execut
i
o
n co
m
p
ared t
o
t
h
e
m
e
t
hods suc
h
as earl
i
e
st
deadl
i
n
e
fi
rst
(ED
F
)
,
fu
nct
i
o
nal
cum
u
l
a
t
i
v
e sche
dul
i
ng an
d t
h
e ot
her sc
hed
u
l
i
n
g
m
e
t
hods awa
r
e of t
h
e pr
o
f
i
t
and
penal
t
y
t
h
at
are
base
d
on
t
h
e sa
m
e
m
odel
.
Th
e
r
e
st
o
f
th
e p
a
p
e
r is
o
r
g
a
nized
as
fo
llo
w
s
: I
n
th
e
second sectio
n, th
e r
e
lev
a
n
t
task
s are r
e
v
i
ew
ed,
an
d
t
h
en
the p
r
op
o
s
ed
algorith
m
is in
trod
u
c
ed
in
t
h
e
th
ird
section
.
In
th
e fou
r
th
sectio
n
,
th
e al
go
rith
m
per
f
o
r
m
a
nce i
s
eval
uat
e
d a
n
d
fi
nal
l
y
i
n
t
h
e
fi
ft
h sect
i
o
n,
t
h
e
co
ncl
u
si
on
an
d
recom
m
endat
i
ons a
r
e
pr
o
v
i
d
ed
.
2.
RELATED WORKS
The real
-t
i
m
e sched
u
l
i
n
g al
g
o
r
i
t
h
m
s
can be
di
vi
de
d i
n
to
two
categ
ories of static an
d
d
yna
m
i
c. In
th
e
st
at
i
c
m
ode, be
fo
re t
h
e o
n
set
of t
h
e sy
st
em
,
t
h
e sche
dul
i
n
g
deci
si
on
s are
m
a
de but
i
n
t
h
e dy
nam
i
c
m
o
de, t
h
e
sche
dul
i
n
g dec
i
si
ons car
ri
ed
out
at
t
h
e t
i
m
e
of sy
st
em
execut
i
on [
8
]
,
[
9
]
.
T
h
e st
at
i
c
al
gori
t
h
m
s
have n
o
use i
n
th
e clou
d co
m
p
u
ting
.
Th
e rest o
f
th
is section in
tro
d
u
ce a few sam
p
les of
dyn
amic alg
o
r
it
h
m
s.
Li
et
al
. [
1
0]
pr
o
pose
d
t
h
e
use
of
pr
oact
i
v
e E
D
F
.
In
t
h
i
s
m
e
t
hod
, sc
h
e
dul
i
n
g
pe
rf
or
m
s
t
h
e t
a
sks
base
d
on the
priority of t
h
em. Thes
e pri
o
rities
are not
a good
re
pre
s
entative to show t
h
e
necessity to perform
a task
, b
ecau
s
e th
e
n
ecessity of a task
is
d
e
te
rmin
ed
pub
licly, and
accord
i
n
g
to
o
t
h
e
r tasks.
Ku
m
a
r et al.
[11
]
propo
se a mu
lti-stag
e al
g
o
rith
m
b
a
sed on
th
e o
l
d
EDF wh
ere th
e
u
s
er
has selected
the VMs
and
pay the costs as
a
m
azon m
odel.
Jens
on
et
al
.
[1
2]
, f
o
r t
h
e
fi
rst
t
i
m
e
i
n
or
de
r t
o
ove
rc
om
e t
h
e de
fi
ci
enci
es i
n
t
h
e
p
r
e
v
i
o
us
al
go
ri
t
h
m
s
,
raised
ano
t
h
e
r criterion
n
a
med
TUF, in wh
ich
th
e so
ft re
al-tim
e sy
stem
tim
econstraints a
r
e s
p
ecifie
d
accurately.
In fact, TUFs a
r
e
a ge
nerali
zed
m
odel in de
ferral pe
riod
which
determ
ine the efficie
n
cy of a tas
k
due
to t
h
e
distance
of task t
o
deferral pe
riod.
Yu et al.
[13
]
, propo
se a task
m
o
d
e
l th
at
co
nsid
ered
bo
t
h
p
r
o
f
it and
pen
a
lty. Acco
rdin
g
t
o
t
h
is
m
o
d
e
l, th
e task
is related
to
two
T
U
F
,
o
n
e p
r
o
f
i
t
TUF a
nd t
h
e ot
her
penal
t
y
TUF. T
h
e sy
st
em
(det
erm
i
n
e
d b
y
the profit func
tion) conside
r
s
the
profit, i
f
t
h
e tas
k
was c
o
m
p
letedaccording to dea
d
li
ne, a
n
d
give
penalty
(det
erm
i
ned b
y
penal
t
y
fu
nc
t
i
on) i
f
t
h
e t
a
sk vi
ol
at
ed dea
d
l
i
n
e o
r
was
r
e
m
oved
bef
o
re
t
h
e deadl
i
ne.
In t
h
i
s
t
a
sk, t
h
e
negat
i
ve
val
u
es
are
u
s
ed
fo
r t
h
e
pen
a
l
t
y
, and a
s
a
r
e
sul
t
,
bot
h T
U
Fs we
re
use
d
i
n
a
si
n
g
l
e
TU
F
.
San
t
ho
sh
et
al. [14
]
prov
i
d
ed
th
e ex
cl
u
s
iv
e sch
e
du
lin
g
o
f
th
e
on
lin
e
real-ti
m
e serv
ices with task
tran
sm
issio
n
.
In
t
h
is typ
e
of alg
o
rith
m
,
if th
e d
e
ad
l
i
n
e
w
a
s vi
ol
at
ed
, t
a
sk i
s
t
r
a
n
sfe
r
r
e
d t
o
a
n
ot
her
vi
rt
ual
mach
in
e,
wh
ich
resu
lts i
n
th
e
i
m
p
r
ov
ed ov
erall syst
em
effi
ci
ency
an
d m
a
xi
m
i
zat
i
on of
t
h
e
ge
neral
use.
Deni
zi
ak
et
al
.
[
15]
pr
o
p
o
s
e
d
t
h
e r
eal
-t
i
m
e sche
d
u
l
i
n
g
a
l
go
ri
t
h
m
usi
n
g
t
h
e e
v
ol
ut
i
o
n
a
ry
ge
net
i
c
s
pr
o
g
ram
m
i
ng.
Thi
s
m
e
t
hod i
s
ope
rat
e
d bas
e
d o
n
t
h
e wo
r
s
t
m
ode. The wo
rst
m
odei
s
t
h
e t
i
m
e
t
h
at
al
l
t
h
e
pr
o
g
ram
s
st
art
e
d si
m
u
l
t
a
neo
u
sl
y
,
t
h
i
s
ass
u
m
p
ti
on i
s
c
o
r
r
esp
o
ndi
ng
t
o
t
h
e si
m
u
l
t
a
neou
s creat
i
o
n
of t
h
e
requ
ests. All the du
ties are
sched
u
l
ed
o
n
a con
s
ta
nt
orde
r a
n
d activate
d
in a
specific tim
e fram
e
.
3.
PROP
OSE
D
APP
R
O
A
CH
One m
e
thod
of the
m
odern dy
nam
i
c algorithm
s
is
th
at, for each task, two
type
s of profit and
penalty
functions are
c
onsi
d
ere
d
.By a
ddi
ng upprofit
and
pe
naltyfo
r
eachtask, the e
xpecte
d
bene
fi
ts are obtaine
d
then
t
h
e t
a
sks
are
s
o
rt
e
d
i
n
t
h
e
or
der
o
f
pre
f
ere
n
ce. I
n
t
h
e e
x
cl
usi
v
e
m
e
t
hods,
w
h
en
t
h
e
ne
w
t
a
sk i
s
e
n
t
e
re
d
wi
t
h
h
i
gh
p
r
iority,
it can
no
t
b
e
p
e
rform
e
d
un
til th
e ex
ecu
tion
task is no
t
fin
i
sh
ed
, bu
t i
n
th
e non
-ex
c
l
u
siv
e
m
e
t
hods
,
by
e
n
t
e
ri
n
g
a
t
a
sk
wi
t
h
hi
g
h
er
p
r
i
o
ri
t
y
, t
h
e
res
o
urces
are
t
a
ke
n
fr
om
t
h
e pr
e
s
ent
t
a
sk
a
n
d
gi
ve
n t
o
task
with h
i
g
h
er priority. Th
ese m
e
th
o
d
s asi
d
e fro
m
th
ei
r adva
ntage
s
,
have challenges s
u
ch as i
n
crease
in the
respon
se tim
e, in
th
e case th
e
n
u
m
b
e
r
o
f
requ
ests
was i
n
creased
.
The p
r
op
ose
d
al
go
ri
t
h
m
,
i
.
e., Ext
e
n
d
ed
of
No
n-
p
r
eem
pt
i
v
e PP-a
w
are sc
hed
u
l
i
n
g (E
NP
P),
whi
c
h i
s
base
d on non-exclusi
v
e sche
duling, attem
p
ts to consi
d
er
t
h
e best type of prioriti
zation for eachtas
k
, s
o
that
th
e task
s with th
e
h
i
gh
est
p
e
nalty
are cancel
ed in the m
i
nim
u
m
tim
e
.
3.
1.
Prop
osed
Al
g
o
ri
thm
Th
e ex
tend
ed
o
f
no
n-ex
cl
u
s
i
v
e on
lin
e sch
e
d
u
ling
p
o
licy
with
th
e
pu
rp
ose to
m
a
x
i
m
i
z
e
th
e ov
erall
syste
m
efficiency. These
policies incl
ude
s the sorti
ng tas
k
s
in the
que
ue, a
nd
cha
n
ge in t
h
e acce
ptance
test at
the tim
e
of the entering a
new ta
sk
duri
ng sc
heduling.
Once
the ta
s
k
s
areaccepte
d t
o
e
n
ter the
queue, t
h
e
pr
o
b
l
e
m
i
s
t
o
h
o
w
a
n
a
p
p
r
op
ri
at
e sche
dul
i
n
g
deci
si
o
n
i
s
adop
ted fo
r m
a
x
i
m
u
m
b
e
n
e
fit.
In
t
h
is algo
rithm
,
th
e
sche
dul
i
n
g
dec
i
si
ons a
r
e m
a
de at
f
o
l
l
o
wi
ng
poi
nt
s:
Task
has
bee
n
success
f
ully com
p
le
ted be
fore
dea
d
line
Reached to t
h
e
critical ti
m
e
of the
exe
c
ution
task
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Title o
f
ma
nu
scrip
t
is sh
o
r
t
an
d clea
r, imp
lies resea
r
ch resu
lts (First Au
tho
r
)
2
293
Th
e critical ti
me is th
e ti
m
e
wh
en
task
ex
ecu
tio
n is
at the
expense
of sy
ste
m
. In
fact,
whe
n
a tas
k
is
per
f
o
r
m
e
d t
oo
l
a
t
e
, i
t
has no
l
o
n
g
er a
n
y
p
r
o
f
i
t
for t
h
e sy
st
em
. Any
l
o
nge
r exec
ut
i
o
n t
i
m
e reduces t
h
e pr
ofi
t
ev
en
if th
e task
was co
m
p
l
e
ted
b
e
fo
re t
h
e d
ead
lin
e. Th
is is sh
own
with
t
critical
, wh
ich
can
b
e
ob
tain
ed
according t
o
E
quation
(1):
t
i
n
f
tt
:ρ
t,
t
ρ
(1
)
At an
y m
o
m
e
n
t
t, th
e ex
p
ected
profit an
d
p
e
n
a
lty to
p
e
rform o
r
can
cel the task
is d
i
fferen
t
. In
th
is
m
o
d
e
, it is b
e
tter th
at th
e d
eci
sio
n
t
o
can
cel
o
r
con
tin
u
e
th
e task
is ad
op
ted
b
a
sed on
th
e
facto
r
s log
i
cally. So
t
h
e rat
i
o
bet
w
e
e
n t
h
e
pr
oba
bl
e l
o
sses agai
ns
t
t
h
e expect
e
d
pr
ofi
t
,
i
s
an i
n
dex t
o
m
easure t
h
e t
a
sk p
r
oc
essi
ng
ri
sk,
w
h
i
c
h i
s
cal
l
e
d ri
sk
fact
or a
n
d s
h
o
w
n
wi
t
h
p, a
nd
o
b
t
ai
ned acc
or
di
ng t
o
t
h
e
f
o
l
l
o
wi
n
g
e
quat
i
o
n
s
. Fi
rst
,
al
l
possi
bl
e m
odes a
r
e e
v
al
uat
e
d acc
or
di
n
g
t
o
E
q
uat
i
o
n
(
2
):
I.
If
(t.+B
→
∗
.
.
.
2
]
II.
if(
+B
,
→
∗
.
2
]
II
I.
D
+w,t+t
t+
→
∗
.
.
.
.
]
(2)
IV.
D
+w,t+B<
+t<t+w
→
∗
.
.
.
.
]
V.
else
→
0
Th
e task
is accep
ted
wh
en th
e Equ
a
tion
(3) i
s
estab
lish
e
d
W+R<D
(
3
)
And t
h
e ri
sk fact
or obt
ai
ned by
Equat
i
on (4), i
s
not
m
o
re t
h
an t
h
e sy
st
em
m
a
xi
m
u
m
ri
sk fact
or
ρ
t,
t
if
t
t
B
t
,B
t
Dt
w
ρ
if
Dt
w
,
t
t
t
B
ρ
0
else
ρ
∞
(4
)
In
ge
neral
,
a
h
i
gh
ri
sk
i
n
t
h
e
sy
ste
m
, can l
ead togreater
profitsas
well aslo
sses.
Differen
t
serv
ice
p
r
ov
id
ers to
lerate v
a
ri
o
u
s
risk
lev
e
ls, and
o
n
l
y th
e task
s with
risk
level lo
wer th
an
th
e to
lerated
risk
or
m
a
xim
u
m
ri
sk fact
or, s
h
ow
n
wi
t
h
p
ma
x
, are accepted and
execute
d, m
e
a
n
ing
that according to Equation
(1),
the task is ca
nc
eled.
The sc
heduling m
e
thod choose a task with
the high
est
expected profit, a
nd only
executed until
the
critical t
i
m
e an
d the m
o
m
e
nt
of e
x
ceedi
ng t
h
e syste
m
tole
rable risk will be rem
oved or c
a
nceled, m
eaning the
m
o
ment that leads to los
s
.
Ther
e
f
ore, at
any
po
in
t of th
e t
s
sche
duling, besides c
h
oosing the task for t
h
e
ex
ecu
tion
,
it is tested
th
at if the cu
rren
t ch
o
i
ce o
f
th
e
risk
wo
u
l
d
in
crease oth
e
r task
s
o
r
no
t, and
rem
o
v
e
th
o
s
e
tasks as
soon a
s
possible
.
If
a request
wa
s rem
ove
d at t
h
e tim
e of
release, the
r
e is no pr
of
it or
p
e
n
a
lty f
o
r
th
e ser
v
i
ce pr
ov
id
er,
whe
n
the
request was accept
e
d for t
h
e proc
ess, there is
the possibility of profit an
d penalty. The profi
t
s are
decrease
d
ove
rtim
e and the costs are inc
r
e
a
sed. T
h
e ov
e
r
all syste
m
efficiency is obtained
by the overall
profit, a
n
d s
hown according t
o
E
q
uation (5):
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 5
,
O
c
tob
e
r
20
16
:
229
1
–
22
99
2
294
P (t)=
0
(
5
)
whe
r
e,
r
(t
ask
rel
easi
n
g t
i
m
e),
D (c
om
pl
et
i
on
deadl
i
n
e
)
,
G(t
)
(t
as
k
pr
ofi
t
)
,
L(t
)
(t
as
k
penal
t
y
) ar
e
t
a
sk
ex
ecu
tion ti
m
e
and
rando
m
v
a
riab
le b
e
t
w
een
th
e b
e
st and
worst ex
ecutio
n
tim
e an
d d
e
term
in
ed
by th
e
p
r
ob
ab
ility d
e
nsity fu
n
c
tion
.
The sc
heduling algorithm
is
sorting the
que
ue base
d
on the prof
it de
nsity according to
Equation
(6),
an
d
each
ti
m
e
a n
e
w task
is en
tered
th
e qu
eu
e, th
e so
rtin
g
is d
o
n
e
ag
ai
n
to
pred
ict wh
ich
task
h
a
s th
e
h
i
gh
er
p
r
o
f
it at the sho
r
test tim
e an
d ach
iev
e
h
i
gh
er profit fo
r t
h
e syste
m
.
A
t
(6
)
Th
ere are two
p
o
s
ition
s
wh
ere th
e
n
e
w request mig
h
t
b
e
accep
ted
:
1)
Sy
st
em
cont
ai
ns s
u
f
f
i
c
i
e
nt
reso
u
r
ces
2) Ne
w
request
ha
d m
o
re
profits than
othe
r a
ccepted
re
que
s
t
s in the
system
In fact
, t
h
e pr
o
pos
ed al
g
o
ri
t
h
m
i
s
areal
-t
im
e sched
u
l
i
n
g al
go
ri
t
h
m
by
havi
n
g
t
i
m
e
-depe
nde
nt
set
of
requ
ests i
n
o
r
der to m
a
x
i
miz
e
th
e system
o
v
e
rall
p
r
o
f
it.
is th
e tim
e wh
en
i
s
est
a
bl
i
s
hed
o
r
rem
oved,
meaning
Σ
.
Suppose t
h
at a set of tas
k
s,
,
,
,…………….
} are the
req
u
e
sts fo
r e
n
tering i
n
to t
h
e
syste
m
, and t
h
e re
quest
rece
ntly entered
i
n
to th
e system
is sh
own
with
T.
,
,
,
,
,
,
,
A(t
0
)
i
s
c
o
nsi
d
ere
d
as
t
h
e
pr
ofi
t
de
nsi
t
y
of
t
h
e
pe
ndi
n
g
re
quest
s
of
t
h
e sy
st
em
at
t
h
e t
i
m
e t
0
,
,
is th
e risk
fact
o
r
, E(Gi(t)) is
th
e exp
ected
profit o
f
Ti, D i
s
th
e co
m
p
leti
o
n
d
e
ad
lin
e and
B is th
e
b
e
st
ti
m
e
an
d
W
is th
e wo
rst ti
m
e
f
o
r ex
ecu
tion
,
an
d
f(c) is
th
e prob
ab
ility d
e
n
s
ity fu
n
c
tio
n
of task
ex
ecu
tio
n
ti
m
e
.
The
ge
neral
pr
ocess
o
f
t
h
e
p
r
op
ose
d
al
go
ri
t
h
m
i
s
sho
w
n
i
n
Al
g
o
r
i
t
h
m
1:
Al
gori
t
hm 1:
The proposed al
gori
t
h
m
pseudo-code (ENPP)
1.
W
h
ile M(T
n
)
∅
2.
E
H
=0;T
H
=T
1
;t
action
=inf;
3.
While
T
i
a.
Calculate E(G
i
(T)) at
schedul
i
ng poi
nt
t
s
b.
If
E(G
i
(T)) >E
H
then
c.
E
H
=E(G
i
(T)); T
H
=T
i
;
d.
End i
f
4.
Sort request M(T
n
) on order A(t0)
5.
End whi
l
e
6.
Calculate
T
H
is t
critical
usi
ng
7.
t
i
n
f
t
t
:ρ
t,
t
ρ
8.
t
action
=m
in{t
critical
،
D
H
};
9.
if (
t
s
+
B
H
+
B
i
>D
i
or
,
)
10
.
usi
ng
11
.
ρ
t,
t
if
t
t
B
t
,
B
t
Dt
w
ρ
if
Dt
w
,
t
t
t
B
ρ
0
else
ρ
∞
12
.
th
en
13
.
Remove T
i
14
.
Execute
T
H
to m
i
n{ T
H
fi
ni
shi
ng t
i
m
e (t
f
)
،
t
action
};
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Title o
f
ma
nu
scrip
t
is sh
o
r
t
an
d clea
r, imp
lies resea
r
ch resu
lts (First Au
tho
r
)
2
295
15
.
If
T
h
does not
fi
ni
sh at
t
action
then
16
.
Abort
T
h
;
17
.
R
e
m
ove T
h
from
18
.
t
s
=t
action;
19
.
else
20
.
t
s
=t
f
;
21
.
End
End
4.
PERFO
R
MA
NCE E
V
ALU
A
TIO
N
In t
h
i
s
sect
i
o
n,
t
h
e ef
fi
ci
ency
of t
h
e
pr
op
ose
d
m
e
t
hod i
s
e
v
al
uat
e
d
usi
n
g e
xpe
ri
m
e
nt
s. Th
e pr
o
p
o
s
ed
algorithm
s
are com
p
ared aga
i
nst ED
F [1
1]
al
go
ri
t
h
m
s
,
an
d no
n
-
excl
usi
v
e on
lin
e sch
e
du
lin
g awar
e
of pr
of
it
and
pe
nal
t
y
al
go
ri
t
h
m
s
cal
l
e
d
NPP
[
12]
.
I
n
t
h
i
s
pa
pe
r, t
h
e
si
ngl
e
seq
u
e
n
ce of
t
h
e
real
-t
im
e rand
om
t
a
sks a
r
e
eval
uat
e
d, wh
e
r
e
i
s
defi
ned
us
i
ng
t
h
e param
e
t
e
rs
i
n
Tabl
e 1.
Tabl
e
1.
Param
e
t
e
rs U
s
ed
i
n
t
h
e P
r
op
ose
d
M
e
t
h
o
d
No Para
m
e
ter
1
[Bi,
W
i
]
Best and wor
s
t execution tim
e
2
Di Relative
deadline
3
e
Task execution ti
me
4
r
Task releas
e ti
m
e
5
Fi(T)
Probability density function
for execution ti
m
e
6
Gi(t)
Profit TUF shows
the task cu
m
u
la
tiv
e profit at the co
mpletion ti
m
e
t
7
L
i
(
t
)
Penalty
T
U
F shows the penalty
caused
by task rej
ection at the ti
m
e
t
Su
pp
ose t
h
at
bef
o
re
dea
d
l
i
n
e Gi
(t
) i
s
a n
o
n
-
asce
ndi
ng
si
ngl
e-m
ode
f
unct
i
o
n,
w
h
i
c
h m
eans
and
0
i
f
Su
pp
ose t
h
at
bef
o
re
dea
d
l
i
n
e Li
(t
) i
s
a
no
n
-
desce
n
di
n
g
one
-as
p
ect
f
unct
i
o
n,
w
h
i
c
h m
eans
and the
task are re
jected i
mmediately after t
h
e
deadline.
The com
p
arative evaluation focuses
o
n
t
w
o
aspect
s:
t
h
e sy
st
em
profi
t
,
an
d t
h
e num
ber
of rem
ove
d
task
s an
d co
m
p
letio
n
tim
e for co
m
p
u
tin
g
t
h
e syste
m
p
r
o
f
it, to
tal pro
f
it, an
d p
e
n
a
lty of all th
e task
s
ob
tain
ed
according t
o
E
quation
(7):
Σ
(7
)
In orde
r
to find
the num
b
er of rem
oved
ta
sks,
t
h
e s
u
m
of tas
k
s ca
nce
l
ed at each
step
obtaine
d
t
h
r
o
u
g
h
t
h
e
al
go
ri
t
h
m
,
t
h
e c
a
ncel
ed
t
a
sks
di
d
n
’t
sc
he
d
u
l
e
d
due
t
o
ha
vi
ng
sc
hed
u
l
i
n
g
pe
nal
t
y
. I
n
or
der
t
o
o
b
t
ain th
e task
co
m
p
letio
n
ti
me, th
e
su
m
o
f
ti
mes lasted
un
til all th
e task
s are sch
e
du
led are con
s
id
ered.
The m
e
t
hod i
s
i
n
suc
h
t
h
at
t
h
e al
gori
t
h
m
i
s
eval
uat
e
d
wi
t
h
10 t
a
s
k
s. Th
en
,
t
h
e num
ber of
i
nput
l
o
a
d
s
is in
creased
un
til th
e n
u
m
b
e
r o
f
task
s reach
e
d
to
1
0
0
,
an
d
test th
e alg
o
rith
m
with
a s
e
t o
f
larg
e task
s, an
d
com
p
are t
h
e s
y
st
em
profi
t
a
nd t
h
e n
u
m
b
er
of
rem
oved t
a
sks as
wel
l
as com
p
l
e
t
i
on t
i
m
e
of t
h
e p
r
o
pos
ed
alg
o
rith
m
to
two o
t
h
e
r algo
ri
th
m
s
.
In
th
e tests, it is assu
m
e
d
th
at g
an
d
l are lin
ear
fu
nct
i
o
ns an
d t
i
m
e
-depen
de
nt tasks
are created
ran
d
o
m
l
y
.
In t
h
ese t
e
st
s, i
t
i
s
assum
e
d t
h
at
t
h
e am
ount
of
an
d
i
s
obt
ai
ne
d
usi
n
g t
h
e E
q
u
a
t
i
ons
(8
)
and (9):
0
(8
)
L
t
0
t
r
a
tr
r
t
D
(9
)
The p
r
o
p
o
se
d al
go
ri
t
h
m
i
s
i
n
fact
t
h
e devel
ope
d f
o
rm
of n
o
n
-
e
x
cl
usi
v
e
o
n
l
i
n
e sche
d
u
l
i
n
g al
go
ri
t
h
m
with sam
e
cha
nge
s.
Th
e
p
r
op
o
s
ed
alg
o
rith
m
in
th
e loop
is simu
lated
to th
e
n
u
m
b
e
r
o
f
100
lo
ad
s i
n
a ti
me d
ead
lin
e
bet
w
ee
n 1
0
-
1
0
0
seco
n
d
s. T
h
e
pr
op
ose
d
al
g
o
r
i
t
h
m
i
s
based on t
h
e n
u
m
b
er of t
a
sk
s ap
pl
i
e
d pe
r sec
o
n
d
.
Thre
e
scenari
o
s are
define
d for this
algorithm
,
the
defi
ned sc
e
n
a
r
ios are
rem
oved based
on three
criteria, the syste
m
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 5
,
O
c
tob
e
r
20
16
:
229
1
–
22
99
2
296
pr
ofi
t
,
t
h
e n
u
m
b
er
o
f
rem
ove
d t
a
sk
s, a
n
d
co
m
p
l
e
t
i
on t
i
m
e
, an
d t
h
e
n
t
h
e
r
e
sul
t
s
ha
ve
be
en a
n
al
y
zed. T
a
bl
e 2
shows
the
propose
d sce
n
ari
o
s.
Tabl
e
2. E
v
al
u
a
t
e
d Sce
n
ari
o
s
Scenario
Descr
i
ption
Targ
et
First scenario
Consider
ing wor
k
l
o
ad fr
o
m
10 to 100 tasks
Overall s
y
ste
m
p
r
o
f
it
Two scenario
Consider
ing wor
k
l
o
ad fr
o
m
10 to 100 tasks
Nu
m
b
er
of r
e
m
oved tasks
Third scenario
Consider
ing wor
k
l
o
ad fr
o
m
10 to 100 tasks
T
a
sks scheduling co
m
p
letion ti
m
e
Fourth scenario
Consider
ing wor
k
l
o
ad fr
o
m
10 to 100 tasks
Correlation coef
f
i
cient i
m
pact
m
easur
e
m
ent
4.
1.
First Sce
n
ari
o
In
t
h
e first scen
ari
o
, th
e t
o
tal p
r
o
f
it
o
b
t
ain
e
d
fro
m
task
s in
th
e t
h
ree m
e
n
tio
n
e
d
m
e
th
od
s
h
a
s been
analyzed.
Thes
e three m
e
thods repeated
with in
crease i
n
th
e n
u
m
b
e
r
o
f
task
s fro
m
1
0
to
1
0
0
,
th
e
resu
lts h
a
ve
been
s
h
o
w
n
i
n
Fi
gu
re 1.
Accord
ing
to
Fig
u
re
1
,
it is
u
n
d
e
rstoo
d
th
at at th
e b
e
g
i
nnin
g
,
th
e system
efficien
cy is raisedb
y
th
e
in
creasing
o
f
l
o
ad
to
th
e m
a
x
i
m
u
m ex
ten
t
and
th
en
it star
ts to
fall.
W
ith
l
o
w l
o
ad, m
a
j
o
rity o
f
task
s meetth
e
d
ead
lin
e an
d th
e system
p
r
ov
id
e b
e
tter pro
f
it,
b
ecau
s
e i
t
sch
e
d
u
l
ed
m
o
re task
s co
mp
letely. Ho
wev
e
r,
b
y
in
creasing
t
h
e
syste
m
lo
ad
, so
m
e
task
s start to
m
i
ss th
e de
adline a
n
d he
nce, the system
encounters
pe
nalty.
More i
n
crease
in the
syste
m
load causes m
o
re
5
be
d
ead
line v
i
o
l
ation
and p
e
n
a
lty an
d lower profit.
Fi
gu
re
1.
C
o
m
p
ari
s
on
o
f
Fi
na
l
Pr
ofi
t
i
n
EN
P
P
,
NPP
,
E
D
F
As sh
ow
n i
n
Fi
gu
re 1,
by
rai
s
i
ngt
he n
u
m
b
er of t
a
sks
,
t
h
e pr
ofi
t
i
s
decrease
d
. The r
easo
n
i
s
ast
h
e t
i
m
e
dem
a
nd of tas
k
s is i
n
crease
d
, the
highe
r
c
o
m
p
etition cau
ses m
a
n
y
task
s d
on’t b
e
co
m
p
leted
on
tim
e a
n
d be
pr
ofi
t
a
bl
e.
H
o
weve
r,
w
h
en
t
h
e sy
st
em
wor
k
l
o
a
d
i
s
l
o
w,
m
o
st
of t
h
e
re
que
st
s fi
ni
s
h
q
u
i
c
kl
y
an
d ca
u
s
e m
o
re
profit.
In
ove
ra
ll, the propose
d
m
e
thod
still m
a
kes m
o
re profit in m
a
ny
m
ode
s tha
n
othe
r m
e
thods.
It is also
u
n
d
e
rsto
od
th
at, EDF h
a
s lowe
r efficiency, beca
use it give
m
o
re p
r
iority to
th
e task
s with
earl
i
e
r dea
d
l
i
n
e, re
gar
d
l
e
ss
of
t
h
e p
r
oba
bl
e
p
r
o
f
i
t
.
He
nce,
e
v
en
wi
t
h
l
o
we
r
dem
a
nd de
nsi
t
y
,
EDF
p
o
st
p
o
n
es t
h
e
task
s co
m
p
leti
o
n
with a
h
i
gh
p
r
ob
ab
ility com
p
ared
to
o
t
h
e
r sch
e
du
ling
meth
od
s.
4.
2.
Second Sce
n
ario
One
of t
h
e
ob
ject
i
v
es i
n
t
h
e
pr
op
ose
d
al
g
o
ri
t
h
m
i
s
t
o
m
i
nim
i
ze t
h
e num
ber
of
re
m
oved t
a
sks.
Thi
s
eval
uat
i
n
g
expe
ri
m
e
nt
has been c
o
nd
uct
e
d u
n
d
er
vari
ou
s wo
r
k
l
o
a
d
s f
o
r al
l
t
h
e al
go
ri
t
h
m
s
, and t
h
e
r
e
sul
t
s
h
a
v
e
b
e
en
show
n in
Figu
r
e
2.
Acco
r
d
i
n
g t
o
t
h
e res
u
l
t
s
, i
t
can be c
oncl
u
d
e
d t
h
at
re
gar
d
i
ng
req
u
est
rem
oval
rat
e
, si
nc
e EDF
gi
ves
h
i
gh
er
p
r
iority to
th
e task
s with
earlier d
e
ad
lin
e, wh
ile
th
e syste
m
wo
rk
lo
ad
is lo
w, it h
a
s th
e lo
west rem
o
v
a
l
rat
e
am
on
g al
l
t
h
e
m
e
t
hods
.
B
y
i
n
creasi
ng
t
h
e n
u
m
b
er of
t
a
sks, t
h
i
s
al
g
o
r
i
t
h
m
i
s
not
capabl
e
of sc
he
d
u
l
i
n
g
and rem
oves
the large
numb
er
o
f
tas
k
s.
Ho
we
ver
,
in
hig
h
wo
r
k
lo
ads, th
e ENPP
alg
o
rith
m
h
a
s b
e
tter
per
f
o
r
m
a
nce.
Bo
th
NPP and
ENPP rem
o
v
e
th
e task
s i
n
three step
s.
When th
e task
is ap
plied
,
th
e am
o
u
n
t
of pro
f
it
and
pen
a
l
t
y
i
s
com
put
ed, an
d i
t
i
s
rem
oved i
f
t
h
e pe
nal
t
y
was hi
g
h
. T
h
e ne
xt
st
ep, i
s
t
h
e t
i
m
e
when t
a
s
k
10
20
30
40
50
60
70
80
90
100
EDF
550
154
167
172
175
156
145
142
134
125
NPP
787
207
287
318
355
370
370
365
358
352
ENPP
142
317
331
352
367
387
381
376
373
371
EDF
NPP
ENPP
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Title o
f
ma
nu
scrip
t
is sh
o
r
t
an
d clea
r, imp
lies resea
r
ch resu
lts (First Au
tho
r
)
2
297
correlation c
o
efficient is
highe
r tha
n
t
h
e
syste
m
m
a
ximum
correlation coefficient,
an
d th
e
fin
a
l st
ep
of
rem
oving is the ti
m
e
when the task is reached to its cr
itical point,
which is whe
n
th
e task sche
duling is at the
ex
p
e
n
s
e
of syste
m
an
d
alth
oug
h
it is
n
o
t
reach
e
d to
th
e
d
e
ad
lin
e,
bu
t th
e t
a
sk
ex
ecu
tion
i
s
no
t in
favo
r
o
f
t
h
e
syste
m
. Since in ENPP m
e
thod, t
h
e corre
lation coe
ffici
ent is obtaine
d with m
o
re
efficient form
ula, the
num
ber
of
t
a
sk
s rem
oved
i
n
t
h
i
s
m
e
t
hod i
s
l
o
we
r t
h
an
t
h
e
ot
he
r al
g
o
ri
t
h
m
s
.
Fi
gu
re
2.
C
o
m
p
ari
s
on
o
f
Ta
s
k
s R
e
m
oval
r
at
e i
n
E
N
P
P
,
NP
P, E
D
F
Fig
u
re 2
sh
ows th
e requ
est rem
o
v
a
lrate an
d
it is
o
b
s
erv
e
d
th
at, wh
en
th
e
n
u
m
b
e
r of tasks is lo
w, th
e
syste
m
is h
a
rd
ly re
m
o
v
e
s th
e
task
s. Bu
t
with in
crease
in
t
h
e d
e
m
a
n
d
,
th
e co
m
p
etitio
n
is en
h
a
n
c
ed
and
hen
ce,
th
e rem
o
v
a
l
rate is in
creased ev
en in
t
h
e
b
e
st
alg
o
rith
m
s
.
4.
3.
Third Scen
ari
o
In
t
h
is scen
ari
o
, th
e co
m
p
letio
n
tim
e o
f
the u
s
ers arem
easure
d
a
n
d evaluated in all
mentioned
m
e
t
hods
. T
h
e e
xpe
ri
m
e
nt
s are re
peat
ed
by
i
n
creasi
n
g t
h
e
n
u
m
ber of t
a
s
k
s
f
r
om
10
t
o
1
0
0
t
a
sks.
Acco
r
d
i
n
g t
o
Fi
gu
re 3, i
n
al
l
m
e
t
hods t
h
e com
p
l
e
t
i
on t
i
mes becom
e
l
onger as t
h
e n
u
m
b
er o
f
t
a
s
k
s
i
n
creases
. B
u
t
for eac
h
num
ber
of t
a
s
k
s, t
h
e p
r
o
p
o
se
d m
e
t
hod s
h
o
w
s
sho
r
t
e
r c
o
m
p
let
i
on t
i
m
e
com
p
ari
ng
ot
he
r m
e
t
hods
.
The
rea
s
o
n
i
s
t
h
at
i
n
t
h
e
ne
w
so
rt
i
n
g m
e
t
hod, t
h
e t
a
s
k
s
wi
t
h
hi
g
h
er
p
r
o
f
i
t
are a
v
ai
l
a
bl
e s
o
o
n
e
r
to
th
e sch
e
du
l
i
n
g
.
Th
ey also are filtered
acco
rd
ing
to
t
h
e n
e
w correlatio
n
co
efficien
t
,
wh
ich
m
a
k
e
s th
em
sch
e
d
u
l
ed
in sh
orter tim
e.
Figure 3
.
Co
mp
ariso
n
of Task
s C
o
m
p
le
tio
n
T
i
m
e
I
n
EN
PP
, N
P
P
,
ED
F
It is also
o
b
s
erv
e
d
th
at
wh
ile th
at th
e work
l
o
ad
is lo
w, th
e
propo
sed
algorith
m
sh
o
w
s p
e
rfo
r
m
a
n
ce at
t
h
e l
e
vel
of
n
o
n
-e
xcl
u
si
ve
onl
i
n
e al
g
o
ri
t
h
m
,
but
w
ith
h
i
gh
er wo
rk
lo
ad
, it’s
p
e
rform
a
n
ce is b
e
tter.
10
20
30
40
50
60
70
80
90
100
EDF
5
1
22
13
34
6
5
66
77
37
8
9
8
NPP
4
9
17
23
31
37
40
46
52
58
ENPP
4
9
15
21
27
34
37
42
50
53
EDF
NPP
ENPP
1234
56789
1
0
EDF
54
64
84
95
102
1
1
4
124
136
144
152
NP
40
42
55
69
83
86.4
9
7
98.2
101
103
ENPP
40
43
52
67.3
8
0
8
2
9
2
9
4
97.8
98.1
EDF
NP
ENPP
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
I
J
ECE
Vo
l. 6
,
N
o
. 5
,
O
c
tob
e
r
20
16
:
229
1
–
22
99
2
298
4.
4.
Four
th Scen
ario
In t
h
i
s
e
xpe
ri
m
e
nt
, t
h
e
ef
fect
of
ri
s
k
fact
or
o
n
t
h
e
efficienc
y
of t
h
e
propos
ed algorithm
is
evaluate
d.
To do
this
t
h
e risk factor p
ma
x
,
was
rai
s
ed
fr
o
m
1 t
o
1
0
a
n
d
t
h
e n
u
m
b
er
of
pr
o
duce
d
t
a
s
k
s
was
eq
ual
t
o
10
0.
The e
x
peri
m
e
nt
was
repeat
e
d
fo
r
one
h
u
n
d
r
e
d
t
i
m
es and t
h
e
ge
neral
i
n
t
e
res
t
of
t
h
e e
x
peri
m
e
nt
i
s
o
b
t
a
i
n
e
d
.
As sh
o
w
n i
n
Fi
gu
re 4
,
t
h
e sy
st
em
profi
t
i
s
decl
i
n
ed
by
h
i
ghe
r ri
sk
fact
or
, fo
r exam
pl
e i
n
p
ma
x
=2
com
p
ared to
p
ma
x
=10, the i
n
terest is increa
sed 1.2 tim
es. The ris
k
fact
or
p
ma
x
decide
d the system
spee
d
response, the l
o
we
r c
o
efficient m
eans a fast
er re
sponse
.H
en
c
e
,
in
th
e
s
y
s
t
e
m
u
n
d
e
r h
i
g
h
w
o
r
k
lo
ad
,
th
e
lo
w
e
r
p
ma
x
shoul
d be
use
d
t
o
achi
e
v
e
bet
t
e
r effi
ci
ency
. Al
t
h
ou
g
h
,
t
h
e expe
ri
m
e
nt
al
resul
t
s
sh
ow t
h
at
a l
o
w
e
r ri
s
k
factor
should
be selected for t
h
e sy
stem
, identification
of a
p
propriate risk
factor
for eac
h
syste
m
is a com
p
lex
an
d im
p
o
r
tan
t
i
ssu
e t
h
at requ
ired
furth
e
r inv
e
stig
atio
n
.
Figu
re
4.
Ef
fec
t
of
Co
rrelatio
n C
o
ef
ficient o
n
E
N
PP
4.
CO
NCL
USI
O
N
A sch
e
d
u
l
er ai
m
e
d
to
fi
n
d
a way to allocate th
e tasks to
th
e limite
d
resources
p
r
o
p
e
rly. Th
e
increasing
num
ber of a
v
aila
ble res
o
urces
a
n
d the c
o
m
putin
g re
quests at t
h
e m
i
nim
u
m
time and
costs
in cloud
com
put
i
n
g
ha
ve em
erged
t
h
e
res
o
u
r
ce al
location and
s
c
heduling as
serious c
h
allenge
s.
When t
h
e
use
r
requests a
r
e
re
al-tim
e, the sc
heduling
proble
m
becom
e
m
o
re
o
b
v
i
o
us.
M
a
ny
al
g
o
ri
t
h
m
s
have
been
pr
o
v
i
d
e
d
fo
r t
h
e real
-t
i
m
e schedul
i
n
g
wi
t
h
t
h
ei
r st
r
e
ngt
hs an
d we
akne
ss. I
n
t
h
i
s
pape
r, d
u
e t
o
t
h
e eval
uat
i
o
n
of t
h
e
problem
s
in each
of t
h
e e
x
isting al
gorithm
s
, a ne
w m
e
thod
nam
e
d ENPP
has bee
n
provi
ded a
nd
re
gardi
n
g the
sy
st
em
overal
l
effi
ci
e
n
cy
, c
o
m
p
l
e
t
i
on t
i
m
e
, an
d t
h
e
n
u
m
ber of t
h
e
r
e
m
oved
t
a
sks
,
i
t
was c
o
m
p
ared
t
o
algorithm
EDF and
non-exclusive
on
l
i
n
e
al
go
ri
t
h
m
aware
of t
h
e
pr
ofi
t
a
nd
pe
nal
t
y
.
Acco
r
d
i
n
g
t
o
t
h
e
expe
ri
m
e
nt
al
resul
t
s
, t
h
e
pr
o
pos
ed m
e
t
hod
red
u
ces t
h
e c
o
m
p
l
e
t
i
on t
i
m
e
and i
n
crea
se
s t
h
e sy
st
em
ove
ral
l
p
r
o
f
it. Th
e
fu
t
u
re st
u
d
i
es cou
l
d
b
e
on
t
h
e alg
o
rith
m
s
with
lo
wer rem
o
v
a
l
rate as
well as th
e abilit
y to
determ
ine the
access level a
n
d sc
he
duling
of eac
h re
source
for t
h
e
user.
REFERE
NC
ES
[1]
K. Mogouie,
et al.
, “A Novel Approach for
Optim
izatio
n Auto-Scaling
in
Cloud
Computing Environmen
t,”
International Jo
urnal of Mod
e
rn
Educa
tion and
Computer Scien
c
e
, vol/issue: 7(8
)
, pp
. 9
,
2015
.
[2]
H. G. Tani
and
C. E.
Amrani, “
C
loud Computing CP
U Allocation and Sch
e
duling Algorithms
using CloudSim
Sim
u
lator,”
International Journal
of
Electrical an
d Comput
er Eng
i
neering
(
I
JECE)
, vol/issue: 6(4)
, 2016
.
[3]
B. B. G. Abad
i
and M. G
.
Aran
i, “Resource Ma
nagement of
IaaS Provide
rs in
Cloud Feder
a
tio
n,”
In
ternationa
l
Journal of Grid
and Distributed
Computing
, vo
l/issue: 8(5), pp. 3
27-336, 2015
.
[4]
H.
Ghiasi and
M.
G.
Arani,
“Sma
rt Virtual
M
achine P
l
ac
e
m
ent Us
ing Le
arning Autom
a
t
a
to Redu
ce P
o
wer
Consumption in
Cloud Data C
e
nters.”
[5]
M.
G.
Arani,
et al.
, “An autono
mic approach f
o
r resource provis
i
oning of cloud
services,”
Cluster Computing
, pp.
1-20, 2016
.
[6]
S.
Ka
to,
et al.
, “
A
loadabl
e
re
al-t
im
e s
c
heduler s
u
ite for m
u
lti
core
platform
s
,
”
Technical Report C
M
U-ECE-TR09-
12, Tech
.
Rep
., 2
009.
[7]
M. G. Arani and M. Shamsi, “An Extended
Approach
for
Efficien
t Data Storage
in Cloud Computing
Environment,”
I
n
ternational Jou
r
nal of Computer
Network and
I
n
formation Secu
rity
, vol/issue: 7(
8), pp
. 30
, 2015
.
[8]
H. Sun,
et al.
, “Research and simulation of task
sc
heduling algo
rithm in cloud computing,”
Indo
nesian Journal of
E
l
ec
t
r
i
c
al
E
n
gi
ne
e
r
i
n
g
and
Computer Science
, v
o
l/issue: 1
1
(11),
pp. 6664-6672
,
2013.
[9]
S.
Pa
l a
nd P.
K.
Pa
ttna
i
k,
“A
Simu
lation-based
Approach to Optim
ize th
e
Execution Time and Minimization of
Average Waitin
g Time Using Queuing M
odel in Cloud Computing Environ
m
ent,”
International Journal of
Electrica
l
and
C
o
mputer Engin
e
ering (
I
JECE)
, v
o
l/issue: 6
(
2), pp
. 743-750
, 2016
.
Normalize
d
profit
Risk
factor
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISS
N
:
2088-8708
Title o
f
ma
nu
scrip
t
is sh
o
r
t
an
d clea
r, imp
lies resea
r
ch resu
lts (First Au
tho
r
)
2
299
[10]
P. Li
, “
U
tili
t
y
a
ccrua
l re
al-
tim
e
sc
heduling: Models
and algor
ithms,”
Doctoral dissertation
, Vir
g
inia Pol
y
t
echn
i
c
Institute
and
Sta
t
e Universi
t
y
,
20
04.
[11]
K.
Kumar,
et a
l
.
, “
R
es
ource
Allo
cat
ion F
o
r Re
al-
T
im
e T
a
s
k
s
Us
ing,”
S
c
hool of
Electrical and Co
mputer
, pp
. 1-5
,
2011.
[12]
M.
Je
nse
n
,
et a
l
.
, “On technical security
issu
es
in cloud computing,” in
2009 I
E
EE Internationa
l Conference o
n
Cloud Computin
g,
pp
. 109-116
,
2009.
[13]
S.
L
i
,
et a
l
.
, “
P
rofit and p
e
na
lt
y
aware sch
e
dulin
g for rea
l
-tim
e o
n
line serv
ices
,”
IEEE Transactions on industrial
informatics
, vol/issue: 8(1), pp. 7
8
-89, 2012
.
[14]
R. Santhosh and
T. Rav
i
ch
andran, “Pre
-em
p
tive
scheduling of o
n
-line r
eal
tim
e
services with
ta
sk m
i
gration for
cloud computin
g,” in
Pa
tt
ern
Recogn
ition
,
Inf
o
rmatics and M
obile
Engin
eeri
ng (
P
RIME)
,
2
013 Internati
o
n
a
l
Conference on
,
pp. 271-276
, 20
13.
[15]
S
.
Denizi
ak,
et a
l
.
, “Cost optimization of
real-tim
e cloud
applicat
ions using develo
pmenta
l gen
e
tic
programming,”
in
Utility and
Cloud Computing (
U
CC)
, 2014 IEEE
/ACM
7th In
ter
national Con
f
erence on
,
pp
. 774-
779, 2014
.
BIOGRAP
HI
ES OF
AUTH
ORS
Fereshteh Hoseini received
the
B.
S.C degree in
Information Tec
hnolog
y
from azad University
of
Arak, Iran in
2004, and M.S.C degree from A
zad University
of mahallat, Iran in 2015,
res
p
ect
ivel
y.
He
r res
earch in
ter
e
s
t
s
include Clou
d Computing, Distributed
S
y
s
t
ems and Softwar
e
Engineering
Mostafa Ghobaei Arani received
the B.S.C d
e
gree
in Software Eng
i
neer
ing from IAU Kashan, Iran
in 2009, and
M.S.C degree from
Azad Univ
ersity
o
f
Tehran
, Ir
an in 2011
, r
e
spectiv
ely
.
He
is a
P
h
D Candidate
in Is
lam
i
c Azad
Univers
i
t
y
, S
c
i
e
nce
and Res
e
a
r
ch Branch
, Te
hran, Iran
.
His
research
int
e
rest
s include
Grid
Com
puting, Clo
ud Computing,
Pervasive Computing, Distr
i
buted
S
y
stems and Sof
t
ware D
e
velopm
ent.
Alirez
a T
a
ghiz
a
d
eh re
ce
ived h
i
s
BS
and M
S
in
Computer Engineering
from Iran University
of
Science and Technolog
y
(IUST) and
Sciences and Resear
ch Branch of Azad
University
(IAU),
Tehran
, Ir
an. H
e
obtained h
i
s PhD in the
area
of Network and
Communication
from University
Sains Malay
s
ia (USM)
in 2013.
He
was for
m
erly
with Iran Telecom.
Research Center (ITRC) as a
S
e
nior Res
e
arch
Engin
eer
in IP
-
b
as
ed cor
e
n
e
tw
orks
. He
is
curr
entl
y
a
le
cture
r
in Is
lam
i
c
Azad
Universit
y
of P
a
rand. His research int
e
rest
s in
clude Cloud co
m
puting, IP m
o
bilit
y
,
h
a
ndover
modeling and
ev
aluation.
Evaluation Warning : The document was created with Spire.PDF for Python.