Internati
o
nal
Journal of Ele
c
trical
and Computer
Engineering
(IJE
CE)
Vol
.
5
,
No
. 3,
J
une
2
0
1
5
,
pp
. 47
7~
48
2
I
S
SN
: 208
8-8
7
0
8
4
77
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
Improved Rejection Penalty Al
gorithm with Multiprocessor
Rejection Technique
Pra
t
i
v
a
Sa
tpat
hy, Ka
l
y
an Da
s, Ja
gmohan Pa
dhi
Departem
ent
of
Com
puter Scien
ce,
Sam
b
alpur
Universit
y
Institu
t
e
of
Inform
ation
Techno
log
y
,
Burla, Sambalpu
r, Orissa, India
Article Info
A
B
STRAC
T
Article histo
r
y:
Received Feb 22, 2015
Rev
i
sed
Ap
r 5, 20
15
Accepted Apr 20, 2015
This pap
e
r de
al
s with m
u
ltipro
cessor schedul
in
g with r
e
je
ction
te
chniqu
e
where each job is provided with
proce
ssing time
and a giv
e
n pen
a
lty
cost. If
the job satisfi
es the ac
cept
a
nc
e c
ondition,
i
t
will
schedule in th
e l
east load
ed
identi
ca
l par
a
ll
el
m
achine
else jo
b is re
je
ct
ed. In
this wa
y its pen
a
lt
y
cost i
s
cal
cula
ted
.
Our
objec
tive
is
to
m
i
nim
i
ze th
e m
a
kes
p
an of
the
s
c
hedul
ed jo
b
and to minimize the sum of the
penaltie
s of r
e
jected
jobs. We h
a
ve merged
‘CHOOSE ‘and
‘REJECTION PENALTY’ algorithm to reduce the sum of
penalties cost
and makespan. Our
proposed
‘Improved Reject penalty
algorithm
’
r
e
duc
e com
p
eti
tiv
e ra
t
i
o, whi
c
h in
turn
enhan
ces
th
e ef
fici
enc
y
of
the on-line algo
rithm. B
y
applying
our new o
n
-
line
technique,
we got th
e
lower bound of our algorithm is is 1.286 wh
ich is far better from the existing
algorithm
s
whose com
p
etitiv
e r
a
tio is at
1
.
819. In our approach we have
consider non-pr
eemption schedu
ling techniqu
e.
Keyword:
Co
m
p
etit
iv
e ratio
Im
prove
d re
jec
t
i
on penal
t
y
Mak
e
sp
an
Off-lin
e sch
e
du
lin
g
On-lin
e sch
e
d
u
lin
g
Rej
ectio
n p
e
n
a
lty
Copyright ©
201
5 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
:
Prativ
a Satp
athy,
Depa
rtem
ent of Com
puter Sci
e
nce,
Sam
b
alp
u
r
Un
iv
ersity In
stitu
t
e
of Inform
at
io
n
Techn
o
l
o
g
y
,
Jyotivihar, B
u
rla, Sam
b
alpur,
India
Em
a
il: p
r
ativ
a.satp
ath
y30
@gmail.co
m
1.
INTRODUCTION
Real ti
me sch
e
d
u
ling
d
eci
d
e
s wh
ich
o
f
th
e p
r
ocesses in
th
e read
y q
u
e
ue is to
b
e
allo
cated
to
th
e
p
r
o
cesso
r and
t
h
e
resu
lt
d
e
p
e
nd
s
o
n
bo
t
h
functio
n
a
l accu
r
acy as well as ti
me requ
ired to
d
e
liv
er th
e
resu
lt.
Ty
pes of
Sc
he
dul
i
n
g:
i)
On
lin
e Sch
e
dulin
g
ii)
Offline Sch
e
du
lin
g
Online
algorit
h
m
processe
s
its input
piece
-by-piece in a
serial fas
h
ion,
without ha
vi
ng the e
n
tire
input
av
ailab
l
e fro
m th
e startin
g.
On
lin
e sch
e
dulin
g
al
g
o
rith
ms
m
a
ke t
h
ei
r s
c
hed
u
l
i
n
g
deci
si
ons
at
r
u
nt
i
m
e, as a
resu
lt of wh
ich th
ere can
b
e
si
g
n
i
fi
cant overheads be
cause
of runtim
e pr
oc
essi
ng
w
h
ere s
c
hed
u
l
i
n
g deci
si
on
s
ar
e
b
a
sed on
dyn
amic p
a
r
a
m
e
ter
s
m
a
y ch
an
ge.
Of
fl
i
n
e sc
hed
u
l
i
ng ha
s com
p
l
e
t
e
kn
owl
e
dge
of t
h
e t
a
s
k
se
ts and its cons
traints; suc
h
as
deadline
s
,
com
put
at
i
on t
i
m
es, prece
den
ce and c
o
nst
r
ai
nt
s, m
u
ch be
fo
re any
deci
si
on
t
h
at
i
s
m
a
de and i
t
do
esn’
t dep
e
nd
on t
i
m
e. Schedul
i
n
g
deci
si
o
n
s are
base
d
on
fi
xe
d pa
ra
m
e
t
e
rs and as
si
gne
d t
o
t
a
s
k
s
m
u
ch be
f
o
r
e
t
h
ei
r
activ
atio
n
.
We h
a
v
e
u
s
ed
a criterio
n
to
m
e
asu
r
e th
e
p
e
rfo
rm
an
ce o
f
on
lin
e alg
o
rithm cal
led
“co
m
p
et
itiv
e
ratio
”. Th
is is j
u
st lik
e th
e ap
pro
x
i
m
a
tio
n
ratio
, co
m
p
aring
th
e obj
ectiv
e v
a
lu
e ob
tain
ed
b
y
on
lin
e algo
rith
m
an
d th
at
o
f
op
timal o
fflin
e algo
rith
m
.
Qu
ality o
f
an
on
-lin
e al
g
o
rithm is tes
t
ed
b
y
ev
alu
a
ting
its worst case an
al
ysis so
th
at th
e co
m
p
etit
iv
e
ratio
is
b
e
tween
o
n
-lin
e
p
e
rform
an
ces o
f
th
e
alg
o
rith
m
to
its op
ti
m
a
l o
f
f-line p
e
rfo
r
m
a
n
ce.
Mathem
atically: -
Compet
it
v
e
Ratio
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
47
7 – 4
8
2
47
8
Perform
a
n
ce c
r
iteria o
f
on
-li
n
e sch
e
d
u
ling
d
e
p
e
nd
on
CPU u
tilizatio
n
,
Th
rou
ghp
u
t
, Tu
rn
-aro
und
ti
me (TAT),
Waitin
g
tim
e (WT).
R. L.
Gra
h
am
et al. [1] i
n
troduce
d
t
h
e fi
rst
dete
rm
in
istic
o
n
-lin
e al
g
o
rith
m
called
as list sch
e
d
u
ling
o
n
lin
e
prob
lem in
wh
ich
h
e
gav
e
a co
m
p
etit
iv
e ratio
o
f
(2
-1
/
m
) w
h
ere
‘
m’
de
n
o
t
e
d t
h
e
n
u
m
b
er of
m
a
chi
n
es
.
The sc
hem
e
pr
op
ose
d
by
D.
D.
Sl
eat
or
an
d
R
.
E.
Ta
rja
n
[
2
]
,
a
d
d
r
esse
d
abo
u
t
t
h
e am
ort
i
zed c
o
m
p
l
e
xi
t
y
of
Least Recently Use
d
al
gorithm
,
provin
g tha
t
the efficiency
of the
propose
d algorithm
differs
from
that of t
h
e
of
fl
i
n
e
pagi
n
g
rul
e
(B
el
ady
’
s
M
I
N al
go
ri
t
h
m
)
, a
n
d
by
a fact
or
t
h
at
depe
n
d
s
o
n
t
h
e
si
ze
of
fast
m
e
m
o
ry
.
D. R. Karg
er et al. [3
] su
gg
est
e
d
th
e co
m
p
etitiv
e ratio
of
u
p
p
e
r bou
nd
t
o
be at aro
und
1
.
94
5.
Y. Bartal et al. [4], introduce
d a
ran
d
o
m
i
zed o
n
line alg
o
ri
thm
s
for a valu
e of m
=
2, where they achieved an
o
p
tim
al co
m
p
e
titiv
e ratio
o
f
4/3
.
Th
e
research
carried
ou
t by S A
l
b
e
rs
[5
], g
a
v
e
t
h
e m
o
st
p
opu
lar b
e
tter
bound
sche
dul
i
n
g p
r
o
b
l
e
m
- t
h
e fun
d
am
ent
a
l
prob
l
e
m
of on-l
i
n
e
al
gori
t
h
m
s
, where a seq
u
e
n
ce of j
o
b
s
has
t
o
be
sch
e
d
u
l
ed
on
'm'-
id
en
tical p
a
rallel
m
ach
in
es to
m
i
n
i
m
i
ze
th
e
m
a
k
e
sp
an
. S A
l
b
e
rs [
6
] pr
opo
sed
an
algo
r
ith
m
called
as th
e M
2
algorith
m
which
g
a
v
e
co
m
p
etitiv
e ratio
of
u
p
p
e
r
b
oun
d as 1
.
92
3.
S. S. Sei
d
en
[7], in
trod
u
c
ed
a
n
e
w con
cep
t of o
n
lin
e
rando
mized
m
u
lt
ip
ro
cesso
r sch
e
du
ling
in
wh
ich
he ga
ve a ran
d
o
m
i
zed al
gori
t
h
m
for a val
u
e
of
m
≥
3
number
of m
achines. In
[8] the a
u
thors int
r
oduced a
n
e
w
v
e
rsion
of
m
u
ltip
ro
cessor sch
e
du
lin
g
with
th
e sp
ecial
featu
r
e
wh
ere t
h
e pro
p
o
s
ed
job
s
m
i
g
h
t
b
e
rejected
at a certain
p
e
nalty. Th
e ob
j
ectiv
e o
f
t
h
e sch
e
d
u
ling
te
c
hni
que wa
s to m
i
nimize the
m
a
kespa
n
of the sc
hedule
for a
n
acce
pte
d
job as
well a
s
to m
i
ni
m
i
ze
the sum
of t
h
e
pe
nalties for rej
ected jobs.
The al
gorithm
h
i
n
t
ed at a l
o
wer
bo
und
o
f
1
.
81
9 fo
r m=3
m
ach
in
e.
In
[9
] au
tho
r
s
in
trodu
ced a
d
e
term
in
istic c
o
n
s
tan
t
co
m
p
etitiv
e o
n
lin
e algo
rith
m
wh
ich
sch
e
d
u
l
ed
a
sequ
en
ce
o
f
job
s
o
n
a
p
r
o
cesso
r ru
nn
ing
at
v
a
riab
le speed
so
as t
o
m
i
nim
i
ze t
h
e c
o
st
of
po
we
r c
ons
um
pt
i
o
n
an
d
th
e
to
tal flow time fo
r all t
h
e
jo
b
s
.Tam
as Nemet an
d
C
s
ana
dIm
r
eh
[1
0]
pr
op
ose
d
a
n
al
g
o
ri
t
h
m
cal
l
e
d ‘C
H
O
O
S
E’
w
h
i
c
h
ga
ve
bet
t
e
r r
e
t
u
r
n
val
u
es
f
o
r t
h
e
param
e
ter
α
, an
d, in
turn
redu
ced
t
h
e m
a
k
e
sp
an
of th
e algo
rith
m
with
Mu
lti-p
r
o
cessor-rej
ection
techniq
u
e
.
In
[1
1]
aut
h
o
r
s
f
o
un
d a
ne
w l
o
w
e
r
bo
u
n
d
f
o
r
m
i
nim
i
zat
i
on of
m
a
kespa
n
f
o
r
a fe
w
num
ber
of
u
n
i
f
orm
l
y
rel
a
t
e
d
machine
.
2.
R
E
SEARC
H M
ETHOD
In t
h
e existing
RP
(
) al
go
ri
t
h
m
,
t
h
ere i
s
an
ope
n
pr
o
b
l
e
m
area f
o
r i
m
pr
ovi
ng t
h
e (
)
v
a
lu
e so
th
at
mak
e
sp
an
is
min
i
m
i
zed
, resu
l
tin
g
in
th
e au
t
o
m
a
t
i
c red
u
c
ti
o
n
o
f
th
e co
mp
etitiv
e ratio
as b
o
t
h
th
e p
a
rameters
are di
rect
l
y
pr
op
o
r
t
i
onal
t
o
e
ach
ot
her
.
T
h
e
o
b
ject
i
v
e
o
f
t
h
e
pape
r i
s
t
o
m
i
nim
i
ze t
h
e m
a
kespa
n
,
whi
c
h i
s
defi
ned as the
total com
p
let
i
on ti
m
e
for all
accepted
j
o
bs
.
It also
m
i
ni
m
i
zes the sum
of the penalties of all
rejecte
d
jobs
.
Notation a
n
d prelimina
r
ies:
J = Set
of
j
o
bs
(Each
j
o
b
has i
t
s ow
n
p
r
oce
s
s
i
ng t
i
m
e and
p
e
nal
t
y
=
,
Processi
ng time of eac
h
job.
Penal
t
y
o
f
eac
h
jo
b.
If
≪
then the
job
is of re
jected
job ot
herwise a
ccepted
job.
m
= num
ber of
m
achi
n
es.
M
(A
) =
Len
g
t
h
of
sum
m
ati
on
of
al
l
pr
oces
s
i
ng tim
e of c
h
osen
hea
v
ily loaded m
achine
∅
G
o
l
d
en Ratio
= 1
.
61
8
∅
1
1.618
1
0
.618
.
= Larg
est Pro
c
essin
g
ti
m
e
b
e
tween all jo
bs.
c = Co
m
p
etitiv
e Ratio
=
.
Prev
ious a
l
gorithms:
Alg
o
rithm
:
Each
j
o
b
i
s
h
a
v
i
ng a
p
r
ocessi
n
g
t
i
m
e and a
pe
nal
t
y
val
u
e
,
i
.
e.
Jo
b
,
.
= 0.618
th
at is
∅
-1
=
, whic
h is
a pa
ram
e
ter used to get a
ccepted and
re
jected
jobs
.
Taki
n
g
‘w
’as t
h
e
penal
t
y
o
f
e
ach
jo
b,
a
jo
b
,
becom
e
s available,
The
job is re
je
cted if
.
, else it is accepte
d a
n
d
sche
dule
d
on a
least loade
d
m
achine.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Imp
r
o
ved Rejectio
n
Pena
lty Alg
o
r
ithm
with Mu
ltip
ro
cessor Rejectio
n Tech
n
i
q
u
e
(
P
r
a
t
i
v
a Sat
pat
hy)
47
9
ist
he
Online
Makes
p
an Pe
rform
a
nce which is
equivalent
to t
h
e
Highest L
o
ad
of summ
ation
of accept
e
d
j
o
bs on t
h
e
processing ti
m
e
of each m
achine
+ summ
at
ion
of Pe
nalties of rej
ected jobs.
M (A
)
+ (1
-1
/m
)
=
<= M (
A
) + (1
-1
/m
)
c = Co
m
p
etitiv
e Ratio
=
.
CHO
O
SE Alg
o
rithm
:
For
gi
ve
n
I=1
,
2…
10 J
o
bs,
G
e
nerat
e
one el
e
m
ent
from
t
h
e i
n
t
e
rval
s
[(i
-
1
)/
10
, i
/
10]
by
un
i
f
orm
di
st
ri
but
i
on
of
pr
ocessi
ng
t
i
m
e
s.
Sto
r
e all th
e
v
a
lu
es
o
n
Set {S1
}
.
Usin
g
techni
que, whe
r
e
=
0
.
61
8,
f
i
nd
sm
alle
st co
st am
o
n
g
I, d
e
no
te it as
*.
In th
e sam
e
way g
e
n
e
rate
o
n
e elem
en
t from
th
e in
terv
al [
-
i/100
,
- ( i-1
)
/1
00
] ,[
+ ( i -1
)
/
1
0
0
,
+
i
/
100]
,
[
∗
- i/1
00
,
∗
-
( i
-
1)/100]
,[
∗
+ ( i-1
)
/100
,
∗
+ i
/
1
0
0
]
fo
r
I
=
1,
2….
1
0.
Sto
r
e all th
e
v
a
lu
es
o
n
Set {S2
}
.
Usin
g
algo
rithm
,
from
{S1
}
, {S2}
, {
and
∗
, g
e
t th
e sm
allest co
st v
a
lu
e fo
r n
e
w al
p
h
a
param
e
ter.
3.
PROP
OSE
D
ALGO
RITH
M
Ou
r P
r
o
p
o
sed
‘Im
pro
v
e
d
R
e
j
ect
i
on Pe
nal
t
y
(IR
P
)’ al
g
o
r
i
t
h
m
i
s
a co
m
b
i
n
at
i
on o
f
bot
h ‘
C
HO
OSE
’
al
go
ri
t
h
m
and
‘R
P (
α
)’
alg
o
ri
thm
.
In
p
u
t
t
o
ou
r al
go
ri
t
h
m
i
s
num
ber
o
f
J
o
b
s
wi
t
h
eac
h
jo
b
ha
vi
ng
i
t
s
p
r
oces
si
ng
t
i
m
e
den
o
t
e
d
by
(
) a
nd
pe
n
a
l
t
y
(
), so
,
.
Wh
en
‘C
HOOSE’ algo
rith
m
is ap
p
lied
,
it will g
e
n
e
rate
on
e elem
en
t fro
m th
e g
i
v
e
n
interv
al [(i
-1)/10, i/1
0
]
for i= {1,
2… 10) num
b
er of jobs wh
ere
processing ti
m
e
with pe
nalty co
st of each
j
o
b (penalty will be is
calcu
lated
b
y
m
u
l
tip
lyin
g
pro
cessing
tim
e
o
f
t
h
e
jo
b wit
h
α
(
0
.
6
18
),
t
a
ken
f
r
om
R
P
(
α
) al
g
o
rith
m. After
p
u
tting
all th
e
j
o
b
s
i
n
th
e abo
v
e
i
n
terv
al, t
h
e resu
lt is stored
i
n
Set {S1}, and
a
v
a
lu
e for
α
*(sm
alle
st cost
val
u
e o
f
{S
1})
i
s
ge
nerat
e
d
.
An
ot
he
r i
n
t
e
r
v
al
[
- i/1
00
,
-
( i-
1
)
/1
00
],
[
+ ( i-1)/
1
00,
+ i
/
100]
,
[
∗
- i
/
100
,
∗
- ( i-
1)/
1
0
0
]
,[
∗
+
( i-
1)/
1
0
0
,
∗
+ i/1
00
] is app
lied
for th
e sam
e
j
o
b
and
th
en
t
h
e
v
a
lu
e is stored
in ano
t
h
e
r
Set {S2
}
.
From
Set
{S
1}
, {S
2}, {
α
}, {
α
*
}
,
wh
ich
is h
a
v
i
ng
less co
st
valu
e, th
at
is taken
as n
e
w al
p
h
a (
α
1)
.
After g
e
ttin
g
n
e
w
alph
a v
a
l
u
e fro
m
‘CHOOSE’
al
g
o
rith
m
,
ch
eck
th
e
co
nd
itio
n
u
s
ing
n
e
w alph
a valu
e,
If
1
.
, Re
ject the
job,
othe
rwise ac
cept it and
sched
u
l
e it i
n
th
e least lo
ad
ed
m
ach
in
e.
The
n
calculate
the On-line m
a
kes
p
an
t
h
at is: - On
-lin
e m
a
k
e
sp
an
(
) = Su
m
of p
r
oc
essi
n
g
t
i
m
e
of hea
v
i
l
y
lo
ad
ed
m
ach
ine + Su
m
o
f
Pen
a
lties o
f
all rej
ected
job
s
.
M
(A
) +
(
1
–
1
/ m
)
Pi < = M
(A
) +
(
1
–
1
/m
)
th
is eq
u
a
tion
is tak
e
n
fro
m
ex
isting
al
g
o
rith
m; we
have
t
a
ke
n t
h
e
sam
e
off-l
i
n
e t
echni
que
.
Co
m
p
etitiv
e Ratio
. (For
find
in
g th
e
v
a
lu
es
of
o
p
tim
al o
ffline, no
rej
ectio
n
is requ
ired
)
Pseudo Code
for our propos
ed
al
gori
t
hm
:
Inpu
t:
N
u
m
b
er of
jobs (i
1, i
2
, i
3
…in)
Ra
ndom
l
y gene
rated
processi
ng time and
pe
nalties for each jobs
,
Fixe
d
num
ber
of
m
achines
(m
)
O
u
t
put
:
To min
i
m
i
ze Co
m
p
etitiv
e-ratio
To m
i
nim
i
ze Make
spa
n
To
m
i
n
i
m
i
ze Pen
a
lties
Me
th
od:
At
t
h
e be
gi
n
n
i
ng
use ‘c
h
oos
e’ al
go
ri
t
h
m
and a
f
t
e
r cal
cul
a
t
i
ng al
l
i
n
t
e
rval
s, fi
nd sm
al
l
e
st
cost
val
u
e a
n
d
d
e
no
tes it as
α
1.
Give t
h
e
random
processing ti
me and t
h
e
penalty to each
job and then apply it to
the rej
ection
technique,
If
1
.
,
Re
ject the
job
Else
Acce
pt t
h
e
job a
n
d sc
hedule it t
o
the
least loade
d
m
achine
‘m
’
Calculate the
sum
of
processing ti
m
e
of a
ccepted jo
bs of heavily
loa
d
ed
m
achine a
n
d pe
nalties sum
of
rejecte
d
jobs
.
On-line m
a
kespan (
= Sum
of
of hea
v
ily loaded m
achine
+ Sum
of
of re
jected jobs.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
47
7 – 4
8
2
48
0
Calculate Off-l
ine m
a
kespan (
Calcu
l
ate c =
Co
m
p
etit
iv
e Ratio
=
.
4.
R
E
SU
LTS AN
D ANA
LY
SIS
For
o
u
r
e
xpe
ri
m
e
nt
we
have
gene
rat
e
ra
n
d
o
m
pro
cessi
n
g
t
i
m
e
and
penal
t
i
e
s fo
r eac
h
j
o
bs.
We
ha
ve
ap
p
lied
n
early abo
u
t
500
00
j
o
b
s
and
calculate th
e
p
e
n
a
lties, m
a
k
e
sap
n
, co
m
p
etitiv
e ratio
of
b
o
t
h
Ex
isting
alg
o
r
it
h
m
an
d
o
u
r propo
sed IRP algo
rithm
.
I
m
p
r
o
v
e
d
Rej
ect p
e
n
a
lty (IRP) g
i
ves less co
m
p
etitiv
e
ratio
, m
a
k
e
sp
an
an
d p
e
n
a
lties co
st.
In
itially we h
a
v
e
g
e
n
e
rated
in
terv
al fo
r CHOOSE al
g
o
rithm
,
after calcu
latin
g
th
e en
tire in
terv
al for
fr
om
{S1}, {S
2}
by
u
n
i
f
orm
di
st
ri
b
u
t
i
o
n
w
h
ere {S
1} a
n
d {
S
2}
re
prese
n
t
i
n
g
t
w
o set
s
,
an
d
gi
ve
n
penal
t
i
es f
o
r
I= {
1
,
2,
1
0
}
jo
bs
, t
h
e
l
o
we
st
cost
val
u
e
i
s
t
a
ke
n f
o
r t
h
e ne
w
param
e
t
e
r ‘
1
’, w
h
i
c
h vari
es
i
n
di
f
f
e
r
ent
p
e
n
a
lties seq
u
en
ce is th
en
pro
cessed
with
CHOOSE al
g
o
rith
m
.
Fo
r
o
n
e
g
i
v
e
n
inpu
t of p
e
n
a
lties, th
e new
al
pha
′1′
param
e
t
e
r i
s
cal
cul
a
t
e
d as ‘
0
.
0
90
’
whi
c
h i
s
bet
t
e
r
t
h
an e
x
i
s
t
i
ng a
l
pha =
0.
61
8.
Ap
pl
i
n
g ne
w a
l
pha
val
u
e i
n
alg
o
r
i
t
h
m
we fou
n
d
th
e su
mm
atio
n
o
f
p
e
n
a
lties is min
i
m
u
m
in
o
u
r case, wh
ich
redu
ces th
e
mak
e
sp
an
and
co
m
p
etitiv
e rat
i
o
in
ou
r
p
r
o
posed
algo
rith
m
.
Fo
r a
g
i
v
e
n
ran
g
e
o
f
j
o
b
with
ran
d
o
m
p
r
o
c
essin
g
ti
m
e
an
d
p
e
n
a
lties, we fou
n
d
o
u
r co
m
p
eti
tiv
e ratio
is l
o
wer th
an
ex
i
s
tin
g
f
o
r fi
xe
d num
ber o
f
machine.
D
a
t
a
set:
In Ou
r ap
pro
a
ch
we
h
a
v
e
ran
d
o
m
ly g
e
n
e
rate pro
cessing
tim
e b
e
tween
1
t
o
5
0
0
an
d p
e
n
a
lties
b
e
tw
een
1
t
o
2
0
0
wh
ich
is
ap
p
lied
o
n
bo
t
h
ex
istin
g and pr
opo
sed I
R
P m
e
th
o
d
for
3 m
ach
in
es and th
e
calcu
lated
m
a
k
e
sp
an, p
e
n
a
lties an
d
co
m
p
etitiv
e ratio
, are g
i
v
e
n
in
Tab
l
e 1
.
Fi
g
u
re 1
co
m
p
ares th
e
Co
m
p
etit
iv
e ratio
b
e
tween
R
P
and
IR
P.
Tab
l
e 2
sho
w
s the calcu
lated
co
m
p
etitiv
e rati
o
using
ex
istin
g
and
IR
P
al
g
o
ri
t
h
m
s
wi
t
h
3, 1
0
, 1
0
0
m
achi
n
es
a
n
d 10
, 10
0, 1
0
0
0
jo
bs
a
n
d
i
n
Tabl
e 3
c
o
m
p
arat
i
v
e
re
sul
t
of
l
o
we
r
b
oun
d in
g
e
n
e
ral f
o
r
3
m
ach
ines is show
n.
Tabl
e 1.
Resu
lts of m
a
k
e
sp
an
, p
e
n
a
lties and
co
m
p
etitiv
e ratio
of
3
m
ach
ines u
s
i
n
g RP and
IRP
NU
MBE
R
OF JO
BS
EXISTIN
G
RP
A
L
GOR
I
T
M
(Co
m
petitive ratio)
PR
OP
OS
D
IRP
A
L
GOR
I
T
HM
(Co
m
petitive ratio)
RP AL
GO
RI
M
(Penaltie
s sum)
IR
P
A
L
GOR
I
T
M
(Penaltie
s sum)
RP AL
GO
RIT
H
M
(on-
l
i
ne makespan
IR
P
A
L
GOR
I
T
HM
(on-
l
i
ne
makespan)
10
1.
8218
1.
224
125
21
317
213
100
16.
05
8.
24
1672
197
3194
1720
500
82.
95
49.
54
7749
1089
1659
9
9930
1000
167.
87
99.
97
1582
9
2262
3357
6
1967
4
1000
0
1619.
5
4
958.
22
4
1533
84
2115
4
3234
57
1987
89
5000
0
7.
9731
6e+03
4.
7140
30+03
7593
66
1075
39
1594
633
9428
06
Fig
u
re
1
.
Co
mp
ariso
n
of C
o
m
p
et
itiv
e ratio
b
e
tween
RP and
IRP
0
500
1000
1500
2000
10
jobs
100
jobs
500
jobs
1000
jobs
10000
jobs
competitive-ratios
[For
fixed machine m=3]
RP
‐
ALGO
IRP
‐
ALGO
Evaluation Warning : The document was created with Spire.PDF for Python.
I
J
ECE
I
S
SN
:
208
8-8
7
0
8
Imp
r
o
ved Rejectio
n
Pena
lty Alg
o
r
ithm
with Mu
ltip
ro
cessor Rejectio
n Tech
n
i
q
u
e
(
P
r
a
t
i
v
a Sat
pat
hy)
48
1
Tab
l
e
2
.
C
o
m
p
arison
o
f
co
m
p
etitiv
e ratio
usin
g RP an
d
IR
P alg
o
rith
m
s
with
3
,
10
,
10
0 mach
in
es and
10,
10
0,
1
0
0
0
j
o
bs
Fixed no.
o
f
ma
c
h
i
n
e
RP-for
10jobs
I
R
P-
for
10jobs
RP-
f
or
100jobs
I
R
P-
for
100jo
b
s
RP-for
1000j
obs
IRP-f
o
r
1000j
obs
M
=
3
1.
821
1.
224
16.
05
8.
24
167.
87
99.
97
M
=
10 1.
494
1.
047
11.
130
3.
723
106.
12
38.
235
M
=
100
1.
435
1.
012
9.
361
1.
954
82.
41
14.
525
Tab
l
e
3
.
C
o
m
p
arativ
e resu
lt
of lower bou
nd
i
n
g
e
n
e
ral for fi
x
e
d m
ach
in
e m=3
LOW
E
R BOUND
OF RP-
ALGOR
ITH
M
LO
WER BO
UND
OF
IRP-A
L
GOR
ITH
M
1.
819
1.
286
5.
CO
NCL
USI
O
N
Th
e
on
-lin
e al
g
o
rith
m
with
l
e
ss co
m
p
etitiv
e ratio and
m
a
k
e
sp
an g
i
v
e
s a b
e
tter p
e
rfo
r
m
a
n
ce
for
real
ti
m
e
d
a
ta’s in
d
i
fferen
t
real ti
m
e
o
n
-
lin
e sch
e
du
lin
g
.
A
new on-lin
e algo
rith
m
called
“Im
p
ro
v
e
d
Rejectio
n
Pen
a
lty” is in
t
r
odu
ced to
enh
a
n
c
e th
e on
-l
in
e efficien
cy
as com
p
are t
o
the e
x
isting
algorithm
for
fixe
d
n
u
m
b
e
r
of m
a
c
h
in
e (3
) with ran
d
o
m
ly g
e
n
e
rated
j
o
b
s
,
p
r
o
c
essin
g
tim
e an
d
p
e
nalties.
We g
e
t l
o
wer
bou
nd
of
o
u
r propo
sed
IRP alg
o
r
ith
m
as 1
.
286
wh
ich
is
m
u
ch
b
e
tter th
an
th
e lower bou
nd
of ex
istin
g
algo
rit
h
m
is ie.
1.
81
9 an
d i
t
i
s
sim
u
l
t
a
neousl
y
m
i
nim
i
zi
ng three
ob
ject
i
v
e
fact
or
s, suc
h
a
s
com
p
et
i
t
i
v
e rat
i
o
, m
a
kespan
and
p
e
n
a
lties as
com
p
ared
to
t
h
e
ex
istin
g RP algo
rith
m
.
The
fut
u
re
w
o
r
k
ca
n
be ca
rri
e
d
out
i
n
t
h
e
f
o
l
l
owi
n
g
di
rect
i
o
ns:
-
Lo
wer b
o
u
n
d
o
f
t
h
e
al
g
o
ri
t
h
m
can be f
u
rt
he
r red
u
ce
d by
ap
p
l
y
i
ng
bet
t
e
r
t
echni
que
.
-
Of
fl
i
n
e al
g
o
r
i
t
h
m
heuri
s
t
i
c
s t
echni
que
ca
n
b
e
im
pro
v
e.
-
It
can
be
sche
d
u
l
e
d
wi
t
h
a
r
bi
t
r
ary
num
ber
of
m
achi
n
es.
-
Reduci
n
g tim
e
and s
p
ace c
o
mplex
ity for m
illions
of
jobs
.
-
It
can
be
i
m
pl
em
ent
e
d u
s
i
n
g
p
r
eem
pt
i
on t
ech
ni
q
u
es
.
REFERE
NC
ES
[1]
R.L. Graham, “Bounds for Certain Mu
ltiprocessor Anomalies”,
Bell S
y
st
em Technical
Journal, Nov.
1966.
[2]
D.D. S
l
eator
an
d R.E. T
a
rj
an,
“
A
m
o
rtized Eff
i
cien
c
y
of
Lis
t
Update and P
a
g
i
ng Rules
”
, Co
m
m
.
As
s
o
ciatio
n
Computing Machiner
y
,
1985.
[3]
D.R. Karger
, S.
J. Phillips and
E. Torng
,
“
A
Bett
er Al
gorithm
for an Ancient
Scheduling Prob
lem
”
, Journal of
Algorithms, 199
6.
[4]
Y.
Bartal,
A.
Fiat,
H.
Karloff and R.
Vohra,
“New Al
gorithms for an Ancient Scheduling Pro
b
lem”, Journal
of
Computer and
Sy
st
em Sciences,
1995.
[5]
S. Albers, “Better bounds for on
line schedu
ling
”
,
SIAM Journal o
n
Computing
, 19
99.
[6]
S. Albers, “
B
etter Bounds for Online Schedul
ing
”
, Proceed
ings of the 29
th
Annual ACM
Sy
mposium on
Theor
y
o
f
Computing, AC
M, 1999.
[7]
S.S. Seiden
, “On
line Random
ized
Multipro
cessor
Scheduling
”
, Al
gorithm
i
ca, 200
0.
[8]
Y. Bart
al,
et
al
.,
“
M
ultiprocessor Scheduling
wit
h
Reje
ctions”
,
P
r
oc. of
the 10
th
Confer
enc
e
on Com
putabilit
y i
n
Europe (C
iE)
20
01.
[9]
S
.
Albers
and
H. F
u
jiwara, “
E
nerg
y-effi
ci
ent algorithms for flow time mini
mization”,
Proc. 23rd International
Symposium on Theoretical
Aspects
of Computer S
c
ien
c
e (
S
TACS)
, Springer LNCS,
2006.
[10]
T. Nem
e
th and C.Im
reh,”Par
am
eter L
earning o
n
-line
algor
ithm
for Multiproce
ssor
Scheduling
with Reject
ion
”
,
Acta C
y
b
e
rnetica 2009.
[11]
J. Schwartz, “Lo
w
er bounds for
online mak
e
span
minimiza
tion
o
n
a small number of related machines”, Springer
2013.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
S
SN
:
2
088
-87
08
IJEC
E V
o
l
.
5, No
. 3,
J
u
ne 2
0
1
5
:
47
7 – 4
8
2
48
2
BIOGRAP
HI
ES OF
AUTH
ORS
Prativa Satp
ath
y
rece
ived B.
Te
c
h
degree from
Biju Patna
i
k Univ
ersit
y
of Te
chno
log
y
, Rourke
la
in 2012. She is currently
pur
suing her M.Tech
from Sambalpur University
Institute of
Information Technolog
y
,
Burla.
Her research in
te
rests are in wir
e
less sensor network and onlin
e
scheduling
algor
ithm.
Kaly
an Das received
the B
.
Te
ch degree from Berhampur University
, B
e
rham
pur in 2005. He
rece
ived M
.
Te
c
h
degre
e
from
People
Educ
ation
Societ
y
Institu
t
e
of T
echno
log
y
, Bang
alore
in
2014. He was working as as associate s
y
s
t
em engi
neer
in IBM India Pvt.
Ltd.
Currently
h
e
is
working as an assistant professor in Sambalpur
University
Institute of Information Technolog
y
,
Burla.
His re
se
a
r
c
h
intere
sts a
r
e in wirele
ss se
ns
or netwo
r
k and on
lin
e scheduling
algor
ithm.
Jagamohan Padhi receiv
ed
M.Sc degree from Sambalpur Univ
ersity
Institute
of Informatio
n
Techno
log
y
, Bu
rla. He
is curren
t
ly
pursuing hi
s PhD in Electron
i
cs from Sambalpur university
Institute of Info
r
m
ation T
echnol
og
y
,
Burl
a. His
research
in
terest
s are
in b
i
oinfor
m
a
tics, on
lin
e
algorithm.
Evaluation Warning : The document was created with Spire.PDF for Python.