Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
7,
No.
2,
April
2017,
pp.
1096
–
1102
ISSN:
2088-8708
1096
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
P
arallel
Genetic
Algorithms
f
or
Uni
v
ersity
Scheduling
Pr
oblem
Artan
Berisha,
Eliot
Bytyc
¸
i,
and
Ardeshir
T
¨
ershnjaku
Department
of
Mathematics,
F
aculty
of
Mathematics
and
Natural
Sciences,
Uni
v
ersity
of
Prishtina,
K
oso
v
o
Article
Inf
o
Article
history:
Recei
v
ed
No
v
21,
2016
Re
vised
Mar
9,
2017
Accepted
Mar
27,
2017
K
eyw
ord:
Genetic
algorithm
P
arallel
computing
Scheduling
problem
ABSTRA
CT
Uni
v
ersity
scheduling
timetabling
problem,
f
alls
into
NP
hard
problems.
Re-sea
rchers
ha
v
e
tried
with
man
y
techniques
to
find
the
most
suitable
and
f
astest
w
ay
for
solving
the
prob-
lem.
W
ith
the
emer
gence
of
multi-core
systems,
the
parallel
implementation
w
as
considered
for
finding
the
solution.
Our
approaches
attempt
to
com
bine
se
v
eral
techniques
in
tw
o
al-
gorithms:
coarse
grained
algorithm
and
multi
thread
tournament
algorithm.
The
results
obtained
from
tw
o
algorithms
are
compared,
using
an
algorithm
e
v
aluation
function.
Con-
sidering
e
x
ecution
time,
the
coarse
grained
algorithm
performed
twice
better
than
the
multi
thread
algorithm.
Copyright
c
2017
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Eliot
Bytyc
¸
i
Department
of
Mathematics,
F
aculty
of
Mathematics
and
Natural
Sciences,
Uni
v
ersity
of
Prishtina
rr
.
N
¨
ena
T
erez
¨
e,
p.n,
K
oso
v
o
eliot.bytyci@uni-pr
.edu
1.
INTR
ODUCTION
Ev
ery
institution
needs
a
s
chedule
to
represent
their
functionality
.
If
the
institution
is
small
and
not
so
comple
x,
the
y
may
choose
to
draft
their
schedule
manually
.
Otherwise,
if
the
institution
is
bigger
and
needs
to
represent
more
comple
x
relations
between
its
functions,
the
y
may
choose
to
use
an
application
that
generates
the
schedule
automatically
.
Ev
en
then,
some
of
the
schedules
are
harder
to
create
and
manage
than
the
others
lik
e
nurse
scheduling
problem
[1].
One
that
f
alls
into
the
hardest
ones,
is
also
the
uni
v
ersity
course
tim
etabling
problem,
which
has
been
pro
v
ed
decades
ago,
that
it
represents
a
NP
problem
[2].
Uni
v
ersity
schedule
needs
to
represent
the
location
and
time
of
all
courses
held
in
a
semester
,
or
year
,
in
the
uni
v
ersity
.
By
doing
this,
it
achi
e
v
es
its
main
goal:
information
of
the
students
and
professors
about
the
lectures
to
be
held.
Another
important
aspect
of
the
schedule,
is
trying
to
accommodate
the
needs
of
the
professors
and
students.
So,
first
consideration
is
on
finding
the
schedule
that
fits
within
uni
v
ersity
w
orking
hours
and
ph
ysical
space
a
v
ailable.
Secondly
,
the
schedule
can
be
impro
v
ed
in
order
to
accommodate
needs
of
the
professors
and
student
s
such
as
not
so
long
w
orking
hours,
not
subsequent
lectures,
taking
i
n
t
o
consideration
breaks
and
e
v
en
personal
preferences
such
as
lectures
in
the
morning
or
in
the
afternoon.
In
[3]
[4]
authors
ha
v
e
described
proposed
usage
of
the
distrib
uted
approach
for
solving
the
uni
v
ersity
timetabling
problem,
mainly
due
to
the
emer
gence
of
multi
core
systems.
Furthermore,
the
y
ar
gue
that
ef
fecti
v
e-
ness
of
the
parallel
processing,
need
to
be
studied
additionally
.
T
aking
this
into
the
account,
we
ha
v
e
proposed
tw
o
v
ersions
of
roulette
genetic
algorithms:
one
based
on
islands
and
the
other
one
on
threads,
to
impro
v
e
solution
of
the
uni
v
ersity
timetabling
problem.
Therefore,
one
of
the
main
aims
of
the
paper
is
to
use
the
paralle
l
processing
algo-
rithm
to
obtain
better
results.
That
has
been
pro
v
en
also
in
[5]
and
[6]
b
ut
our
solution
represe
nts
first
of
all
a
fusion
of
a
model
used
in
[5]
and
another
in
[6]
and
in
addition
the
tournament
usage
is
done
in
multi
thread.
According
to
our
e
xp
e
riments
the
tournament
selection
method
allo
ws
for
v
ery
quick
solutions
in
light-constrained
problems,
using
a
fine-grained
parallelism
method,
and
roulette
selection
can
be
used
in
a
coarse-grained
parallel
algorithm
with
slightly
slo
wer
b
ut
better
results
in
e
v
en
harder
problems
Therefore,
the
adv
antage
of
our
model
is
in
cases
of
bigger
population.
This
paper
is
further
or
g
anized
as
follo
wed:
section
2
describes
the
related
w
ork
on
the
problem
with
empha-
sis
on
genetic
algorithms
used.
Section
3
de
scribed
in
depth
the
problem
and
its
constraints,
while
section
4
describes
J
ournal
Homepage:
http://iaesjournal.com/online/inde
x.php/IJECE
I
ns
t
it
u
t
e
o
f
A
d
v
a
nce
d
Eng
ine
e
r
i
ng
a
nd
S
cie
nce
w
w
w
.
i
a
e
s
j
o
u
r
n
a
l
.
c
o
m
,
DOI:
10.11591/ijece.v7i2.pp1096-1102
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
1097
algorithms
used.
In
section
5
results
from
e
xperiments
are
presented
and
section
6
represents
the
conclusion
and
future
w
ork.
2.
RELA
TED
W
ORK
Solving
uni
v
ersity
schedule
has
been
attempted
in
se
v
eral
w
ays,
by
using
dif
ferent
kind
of
algorithms.
In
[7],
authors
ha
v
e
used
particle
sw
arm
optimization
algorithm
with
local
search.
T
w
o
types
of
the
particle
sw
arm
optimization
ha
v
e
been
e
v
aluated
and
the
obtained
results
were
satisf
actory
,
both
for
teachers
and
classes.
It
should
be
emphasized
that
all
conflicts
ha
v
e
been
handled,
e
v
en
though
in
the
case
when
the
local
search
w
as
added,
the
satisf
action
w
as
better
.
A
specific
case
study
of
an
Italian
school
timetable
w
as
presented
by
the
authors
of
[3],
by
using
genetic
algorithms.
Ev
ery
single
one
of
their
solutions
generated
by
the
algorithm,
ha
v
e
met
the
required
constraints.
The
penalty
for
e
v
ery
constraint
w
as
set,
from
the
ones
with
the
highest
importance,
such
as
tw
o
teachers
in
the
same
class
in
the
same
hour)
to
the
less
significant
ones
such
as
teacher
specific
preference,
which
had
a
smaller
penalty
.
The
y
ha
v
e
also
used
mutation
and
crosso
v
er
operators
b
ut
with
some
restrictions
due
to
the
initialization
phase.
In
another
paper
[8],
a
parallel
genetic
algorithm
w
as
used
in
order
to
minimize
one
of
the
biggest
fla
ws
of
genetic
algorithm,
time
needed
to
obtain
the
result.
According
to
the
study
,
time
w
as
ef
ficiently
reduced
using
commercial
shared
memory
multiprocessor
.
In
the
algorithm
the
chromosome
is
di
vided
into
n
parts,
e
v
ery
part
consisting
of
m
tuples.
The
operators
used
are
mutation
and
crosso
v
er
operator
and
the
constraints
presented,
as
the
authors
conclude
themselv
es,
are
not
the
only
ones
to
be
used
in
a
real
case.
Besides
the
usual
usage
of
the
operators
for
gene
muta
tion,
authors
in
[9]
ha
v
e
used
another
type
of
operators
called
a
bad
genes
operator
that
changes
the
genes
that
cause
hard
constraint
violations.
Such
an
operator
is
said
to
ha
v
e
impro
v
ed
the
performance
of
algorithm.
This
approach
has
been
considered
also
in
our
case.
Genetic
algorithm
w
as
used
to
solv
e
the
school
timetable
problem
[5],
where
roulette
wheel
w
as
used
for
selection
purpose.
So,
the
best
parents
will
ha
v
e
better
probability
to
get
selected
and
therefore
allo
wing
for
better
solutions
to
be
achie
v
ed.
This
method
w
as
used
in
our
case
as
well.
In
one
of
latest
papers
[6]
on
the
problem
of
school
timetable,
authors
ha
v
e
used
a
parallel
genetic
algorithm
in
a
high
performance
parallel
computing
machine
created
from
personal
computer
hardw
are,
Beo
wulf.
Their
fitness
function
is
used
to
sum
all
the
penalties,
while
the
tournament
w
as
chosen
to
select
parents,
combined
with
number
of
operators
such
as
mutation,
crosso
v
er
and
reproduction
to
create
a
successor
.
The
algorithm
model
w
as
coarse-grain
parallel
model.
Challenging
the
results
from
this
paper
,
our
algorithm
will
be
tried
in
a
personal
computer
with
re
gular
performance
and
comparing
tw
o
algorithms:
coarse-grained
parallel
and
multi
thread
with
tournament.
3.
DESCRIPTION
OF
THE
PR
OBLEM
The
problem
of
the
scheduling
consists
of
se
v
eral
elements
that
comprise
it,
professors,
student
groups,
classrooms,
subjects
taught
by
professors
and
related
constraints
between
them.
In
the
follo
wing,
requirements,
terms
used
and
constraints,
will
be
defined.
A
group
represents
certain
number
of
students;
which
number
depends
on
e
x
ercis
es
to
be
held:
numerical
or
laboratory
.
Numerical
groups
can
be
up
to
30
students
b
ut
not
belo
w
20
students,
while
laboratory
groups
can
be
up
to
15
students
b
ut
not
belo
w
10
st
udents.
F
or
the
lectures,
the
abo
v
e
mentioned
groups,
ha
v
e
to
be
mer
ged
A
classroom
consists
of
limited
capac
ity
of
seats,
where
not
e
v
ery
group
can
be
accommodated
in
those
class-
rooms.
Besides
that,
classrooms
can
be
usual
for
numerical
e
x
ercises
and
lectures,
while
l
aboratories
are
usual
for
laboratory
e
x
ercises
A
professor
can
be
lecturer
or
teaching
assistant
A
subject
is
a
teaching
course
taught
to
a
group
by
professor
in
certain
time
A
period
is
timetable
slot,
which
tells
the
maximum
number
of
courses
(both
lectures
and
e
x
ercise)
during
w
orking
day
A
w
aiting
period
is
a
time
slot
which
represents
maximum
w
aiting
time
between
tw
o
consecuti
v
e
lectures
Each
schedule
is
defined
in
terms
of
professors,
classrooms,
students,
period
and
w
aiting
time.
Therefore,
se
v
eral
problems
can
arise
such
as
the
one
described
abo
v
e
re
g
arding
limited
capacity
of
seats.
Other
problems,
such
P
ar
allel
Genetic
Algorithms
for
Univer
sity
Sc
heduling
Pr
oblem
(Artan
Berisha)
Evaluation Warning : The document was created with Spire.PDF for Python.
1098
ISSN:
2088-8708
as
o
v
erlapping
of
time
for
the
same
subject,
same
classroom,
same
professor
and
same
group
of
students.
Further
-
more,
the
sequence
(classroom,
professor
,
group
of
students,
subject)
must
be
ass
igned
a
time
and
day
.
This
requires
fulfilment
of
man
y
constraints,
that
can
be
di
vided
into
hard
and
soft
ones.
By
hard
constraints
are
defined
all
those
mentioned
abo
v
e.
In
other
hand,
soft
constraints,
represent
all
other
constraints
that
e
v
en
when
not
fulfilled,
do
not
af
fect
the
schedule
operability
.
3.1.
Constraints
used
As
in
[10],
these
constraints
are
di
vided
in
four
main
groups:
T
ime,
Courses,
Subjects,
and
Resources.
The
T
ime
is
di
vided
into
time
slots,
considering
it
as
number
of
sequences
of
nonne
g
ati
v
e
inte
ger
for
number
of
time
slots
per
day
,
and
the
day
represents
the
day
of
the
week.
A
Course
it
is
a
collection
of
e
v
ents
together
with
the
group
of
students
and
subject.
Subject
are
represented
as
Mathematics,
Informatics
and
Resources
are
meant
for
students,
teachers
and
classrooms.
W
e
di
vided
constraints
in
tw
o
main
groups:
hard
and
soft.
By
hard
we
mean
the
requirements
lik
e
there
has
to
be
no
conflict
in
lecture
time
for
professor
.
Otherwise
with
soft
constraint
we
define
requirements
lik
e
w
aiting
period.
The
list
of
hard
and
soft
constraints
is
follo
wing:
Hard
constraints:
No
conflict
in
lecture
time
for
professors
No
conflict
in
lecture
time
for
classrooms
A
group
cannot
be
in
tw
o
lectures
at
the
same
time
Number
of
students
cannot
e
xceed
the
number
of
seats
of
a
classroom
Laboratory
e
x
ercises
should
be
held
in
laboratories.
Soft
constraints:
Not
to
ha
v
e
lectures
and
e
x
ercise
of
the
same
subject
within
the
same
day
If
there
is
no
need
for
lectures
to
be
held
in
laboratory
,
then
the
classroom
mustnt
be
laboratory
W
aiting
time
for
a
professor
should
not
e
xceed
more
than
tw
o
hours
W
aiting
time
for
group
should
not
e
xceed
more
than
tw
o
hours.
4.
ALGORITHMS
USED
Algorithms
used
are
based
on
the
basic
roulette
wheel
selection.
Initially
it
creates
a
population
by
generating
indi
vidual
instances
randomly
.
Instances
are
e
xamined
and
their
v
alues
are
assigned
based
on
the
heuristic
function.
Heuristic
function
return
smaller
v
alues
for
better
instances
b
ut
in
order
to
compute
the
cost,
the
v
alue
is
in
v
ersed
so
that
the
best
instances
ha
v
e
the
biggest
v
alue.
The
w
orst
instance
has
v
alue
of
1.
Obtained
v
alues
are
used
as
interv
als
for
the
roulette
function,
which
assigns
randomly
indi
viduals
as
parents.
Since
better
instances
ha
v
e
bigger
v
alues,
the
chance
for
creation
of
better
indi
viduals
is
greater
.
The
ne
wly
created
generat
ion
is
based
on
the
parents
chosen
and
the
crosso
v
er
process.
4.1.
F
ormal
encoding
of
the
r
eal
scheduling
pr
oblem
in
terms
of
genetic
paradigm
constraints
used
In
term
s
of
m
odelling,
instances
describe
a
whole
indi
vidual
schedule
whereas
genes
sho
w
for
a
specific
lecture
time
and
class
room.
Re
g
arding
the
selection
and
the
fitness
functions,
it
should
be
noted
that
roulette
wheel
selection,
implemented
with
whole
inte
gers,
is
used
on
all
cases
e
xcept
on
the
asynchronous
mul
ti
thread
instance
where
the
whole
population
is
man-aged
by
dif
ferent
threads.
Those
threads
dont
synchroni
ze
between
generations
and
thus
must
use
tournament
selection
as
a
selection
method
that
allo
ws
for
asynchron
y
because
it
doesnt
need
to
sort
the
whole
population
or
find
the
sum
of
the
entire
populations
fitness.
The
fitness
function
returns
an
inte
ger
,
depending
on
ho
w
man
y
constraints
are
violated.
The
returned
inte
ger
is
higher
because
its
a
simple
sum
of
weighted
constraint
violations,
where
for
each
violation
the
sum
is
increased
by
P
h
or
P
s
points,
where
P
h
is
the
penalty
for
violating
a
hard
constraint
and
P
s
the
penalty
for
violating
a
soft
constraint.
Because
of
the
specific
conflict
elimination
crosso
v
er
used
in
this
e
xperiment,
and
because
the
fitness
function
of
all
indi
viduals
is
measured
well
IJECE
V
ol.
7,
No.
2,
April
2017:
1096
–
1102
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
1099
before
the
yre
crossed
o
v
er
,
it
is
the
fitness
functions
responsi
b
i
lity
to
also
mark
with
an
additional
number
each
gene
that
has
been
found
to
represent
a
class
that
violates
some
constraint,
the
mark
er
can
be
called
conflict-mark
er
.
The
same
mark
er
is
used
in
the
crosso
v
er
procedure,
wherein
the
higher
the
conflict
mark,
the
less
the
chances
of
the
gene
are
to
be
used
in
the
child,
and
usually
if
a
gene
of
a
parent
has
a
high
conflict-mark
er
it
gets
replaced
with
the
other
parents
gene
that
represents
the
same
lecture,
b
ut
in
a
dif
ferent
time
or
place,
thus
hopefully
eliminating
the
conflict
much
f
aster
.
F
ormally
conflicts
are
presented
in
such
a
w
ay
that
for
e
v
ery
lecture
that
violates
a
constr
aint,
a
mark
er
is
used
to
represent
the
le
v
el
of
constraint
that
has
been
violated
in
the
gene
that
represents
that
specific
lecture.
F
or
hard
constraints
the
mark
er
gets
a
higher
v
alue
than
for
soft
constraints.
A
gene
conflict
represents
lectures
that
do
not
fulfil
an
y
constraint.
4.2.
Cr
osso
v
er
Crosso
v
er
method
for
conflict
elimination
is
based
on
uniform
crosso
v
er
[11]
b
ut
with
an
additional
condition
which
penalizes
selection
of
genes
with
conflicts.
This
allo
ws
substitution
of
genes
with
conflict
of
one
of
the
parents
with
the
genes
from
the
other
parents,
that
ha
v
e
less
or
no
conflicts.
In
this
case,
e
v
ery
gene
of
e
v
ery
parent
is
tried
and
compared.
So,
if
the
v
alue
of
the
conflict
of
a
parent
gene
is
lo
wer
than
the
v
alue
of
the
conflict
of
the
other
parent,
then
that
gene
is
selected
for
the
ne
w
indi
vidual.
But,
if
the
v
alue
of
the
conflict
is
the
same
then
the
gene
of
ne
w
the
indi
vidual
in
that
position
is
not
changed
for
t
he
sak
e
of
ef
ficienc
y
.
The
crosso
v
er
operator
can
be
e
xpressed
with
the
follo
wing
pseudocode:
crosso
v
er
(parent1,
parent2):
child
=
cop
y(parent1)
for
i
=
0
to
N
do
if
parent1.gene[i].conflict()
¿
parent2.gene[i].conflict()
do
child.gene[i]
=
parent2.gene[i]
return
child
Besides
the
crosso
v
er
operator
,
algorithms
use
also
another
operator
called
mutation
first
fit.
4.3.
Mutation
first
fit
Mutation
first
fit
is
used
to
fix
the
time
and
classes
in
which
the
lectures
will
be
held,
by
using
mutation,
in
order
to
achie
v
e
an
acceptable
timing
and
place
and
therefore
impro
v
e
the
schedule
and
e
v
entually
achie
v
e
optimal
schedule.
T
o
achie
v
e
the
appropriate
class
for
the
lecture,
the
requirement
for
the
lecture
are
tak
en
into
the
account.
If
the
lecture
requests
a
bigger
class,
then
it
should
be
chosen
from
the
classes
that
can
accommodate
that
request.
It
is
the
same
also
in
the
case
when
a
lab
is
needed
for
the
lecture.
But,
there
e
xists
also
the
possibility
that
the
class
can
be
changed
randomly
in
order
not
to
be
block
ed
in
one
class
that
is
appropriate
b
ut
doesnt
ha
v
e
free
time
slots.
4.4.
Coarse
grained
Coarse
grained
algorithm
or
island
algorithm,
creates
se
v
eral
instances
of
roulette
based
genetic
algorithm,
which
are
called
islands
because
its
population
can
communicate
only
through
the
managing
algorithm.
In
e
v
ery
island,
on
e
v
ery
nth
generation,
best
instance
migrates
in
all
other
islands.
This
increases
the
chance
that
the
population
in
general
doesnt
get
stuck
on
local
maximums.
On
the
other
hand,
it
allo
ws
the
best
schedules
to
become
part
of
other
is-lands
b
ut
also
allo
ws
islands
to
di
v
er
ge
considerably
from
each
other
.
4.5.
Multi
thr
ead
with
tour
naments
The
total
population
with
n
indi
viduals
is
di
vided
and
managed
by
k
threads,
with
the
responsibility
o
v
er
t
=
n/k
indi
viduals.
Ev
ery
thread
manages
a
time
interv
al
of
the
population
[t*i,
t*(i+1)-1],
where
i
the
inde
x
of
the
thread.
Ag
ain,
the
schedules
are
generated
randomly
and
then
crosso
v
er
and
mutation
are
applied
to
create
the
ne
w
indi
vidual.
The
best
indi
vidual
is
remo
v
ed
from
the
replacement
loop,
because
of
elitism.
The
follo
wing
pseudocode
describes
the
multithread
with
tournament
algorithm:
best
=
find
best
indi
vidual
from
populat.
[t*i:t*(i+1)-1]
for
e
v
ery
indi
vid
in
population
[t*i:t*(i+1)-1]:
if
indi
vidual
==
best,
go
to
ne
xt
indi
vidual
P
ar
allel
Genetic
Algorithms
for
Univer
sity
Sc
heduling
Pr
oblem
(Artan
Berisha)
Evaluation Warning : The document was created with Spire.PDF for Python.
1100
ISSN:
2088-8708
choose
parent1
with
tournament
with
p=2
contenders
from
the
o
v
erall
population
choose
parent2
with
tournament
with
p=2
contenders
from
the
o
v
erall
population
child=
crosso
v
er(parent1,
parent2)
child.mutation(fraction
OfGenesPerMutation)
4.6.
Algorithm
e
v
aluation
In
the
end,
in
order
to
compare
the
results,
we
can
quantify
the
performance
of
the
algorithm,
with
the
follo
wing
formulae:
V
P
=
(
V
T
+
29)
P
+
T
(1)
Where
VP
represents
v
alue
after
penalization
and
VT
,
the
v
alue
of
timetable,
P
represents
penalization
and
T
time
in
seconds.
So,
the
minimal
v
alue,
which
can
be
reached
if
all
constraints
are
satisfied
in
the
timetable,
is
-29.
The
v
alue
-29
is
g
ained
from
fi
v
e
hard
constraints,
each
represented
by
5
points
and
four
soft
constraints,
each
represented
by
1
point.
The
penalization
when
all
constraints
are
satisfied,
is
only
the
time
e
xpressed
in
seconds,
and
the
v
alue
of
penalization
increases
for
each
point
a
w
ay
from
the
minimal
v
alue.
In
other
hand,
to
find
the
most
accurate
performance
v
alue
of
an
algorithm
parame
ter
,
one
should
tak
e
the
sum
of
all
performances
of
that
algorithm
(e
x
ecuted
se
v
eral
times)
and
finding
its
a
v
erage
v
alue.
After
what,
it
can
be
compared
with
other
parameters
a
v
erage
and
the
lo
west
v
alue
describes
the
best
performance
of
that
specific
parameter
.
5.
RESUL
TS
FR
OM
THE
EXPERIMENTS
The
algorithms
used
for
the
uni
v
ersity
scheduling
problem,
where
tried
in
a
personal
computer
with
the
I5
processor
and
4
Gb
of
RAM.
Beforehand,
se
v
eral
e
xperiments
to
ackno
wledge
the
important
parameters
where
performed.
After
that,
important
parameters
were
used
to
perform
a
set
of
e
xperiments,
which
g
a
v
e
the
follo
wing
results.
5.1.
Results
fr
om
coarse
grained
algorithm
The
coarse
grained
algorithm
results
are
sho
wn
in
T
able
1.
Population
v
alues
chosen
were
100,
200,
400,
600
and
800.
F
or
those
v
alues,
after
se
v
eral
tests
we
ha
v
e
obtained
the
best
results.
In
all
cases,
algorithm
has
performed
optimally
finding
the
best
v
alue
possible,
which
is
-29
when
all
constraints
are
fulfilled.
The
best
time
performance
has
resulted
in
case
of
population
400.
Ev
en
though,
the
dataset
used
in
our
paper
cannot
be
compared
to
an
y
specific
dataset
used
in
other
cases,
for
e
xample
in
[5],
we
can
ar
gue
on
the
results
that
as
bigger
the
population,
the
time
to
achie
v
e
the
best
result
is
increased,
similarly
to
the
results
in
[5].
T
able
1.
Results
from
coarse
grained
algorithm
Population
V
alue
Generation
Gene
mutation
T
ime
in
seconds
100
-29
873
60
39.569
200
-29
3397
60
248.241
400
-29
248
60
42.523
600
-29
330
40
86.926
800
-29
254
40
86.619
5.2.
Results
fr
om
multi
thr
ead
with
tour
nament
algorithm
Also
when
dealing
with
the
multi
thread
tournament
algorithm
(four
threads)
with
period
eight
(maximum
number
of
courses
during
w
orking
day)
and
class
mutat
ion
1/5,
we
ha
v
e
obtained
results
as
sho
wn
in
T
able
2.
Popula-
tion
v
alues
chosen
were
same
as
pre
vious:
100,
200,
400,
600
and
800.
Als
o
multi
thread
algorithm
in
e
v
ery
case,
has
performed
optimally
finding
the
best
v
alue
-29.
The
best
result
w
as
obtained
in
the
case
of
population
800.
In
the
case
of
multi
thread
tournament
algorithm,
a
Crosso
v
er
with
conflict
gene
remo
v
al
has
been
adapted
from
the
graph
colouring
problems
and
has
sho
wn
impro
v
ement
in
t
he
timetable
problem,
compared
to
splice
crosso
v
er
and
uniform
crosso
v
er
.
The
time
to
achie
v
e
the
results
is
decreasing
as
well
as
the
number
of
generations
created.
IJECE
V
ol.
7,
No.
2,
April
2017:
1096
–
1102
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
1101
T
able
2.
Results
from
multi
thread
tournament
algorithm
Population
V
alue
Generation
Gene
mutation
T
ime
in
seconds
100
-29
873
40
46.406
200
-29
254
40
27.277
400
-29
458
80
83.513
600
-29
177
40
48.587
800
-29
86
60
29.919
T
able
3.
Mean
score
for
coarse
grained
and
multi
thread
tournament
algorithm
Population
Coarse
Grained
(Mean
score
in
seconds)
Coarse
Multi
thread
T
ournamnet
(Mean
score
in
seconds)
100
527.60075
809.151
200
123.76925
335.29625
400
187.77375
508.424
600
351.903
443.14875
800
201.9715
148.04225
6.
CONCLUSION
AND
FUTURE
W
ORK
F
or
e
v
ery
population
we
calculated
the
score
v
alue
for
both
al
gorithms
using
equation
(1)
in
Section
3,
then
we
took
the
mean
v
alue
o
v
erall
cases,
as
presented
in
T
able
3.
Comparing
results,
we
can
s
ee
that
Coarse
grained
algorithm
is
almost
twice
better
then
Multi
thread
T
ournament
algorithm.
Although
the
multi
thread
computing
should
be
f
aster
.
The
Coarse
grained
algorithm
fulfilled
both
hard
and
soft
constraints
in
60%
of
cas
es,
while
fulfilment
of
hard
constraints
and
not
all
soft
constraints
is
achie
v
ed
within
95%
of
cases.
The
Multi
thread
T
ournament
algorithm
fulfilled
both
hard
and
soft
constraints
in
45%
of
cases,
while
ful
filment
of
hard
constraints
and
no
t
all
soft
constraints
is
achie
v
ed
within
65%
of
cases.
Based
on
these
findings
and
T
able
3
we
conclude
that
in
this
scheduling
problem,
Coarse
Grained
Algorithm
is
more
ef
fecti
v
e
and
ef
ficient
than
Multi
Thread
T
ournament
Algorithm.
As
pre
viously
concluded,
the
coarse
grained
algorithm
w
as
pro
v
ed
more
ef
fecti
v
e
and
ef
ficient
due
to
the
f
act
that
it
can
use
roulette
selection
and
which
cannot
be
used
in
fine
grained,
in
which
tournament
can
be
used.
Therefore,
we
ha
v
e
not
used
the
ob
vious
case
of
comparing
coarse
grained
with
fined
grained
through
tournament,
since
it
w
ouldnt
mak
e
much
sense
if
the
roulette
is
better
in
more
dif
ficult
problems.
As
well
from
our
case,
the
roulette
has
often
pro
v
en
to
find
better
solutions
or
didnt
get
block
ed
on
local
maximums.
F
or
future
w
ork,
since
the
algorithm
has
unpredicted
output
we
will
use
this
property
to
generate
k
e
ys
for
v
a
rious
cryptographic
algorithms.
This
will
speed
up
the
encryption/decryption
time
also
will
increase
security
of
these
algorithms
because
of
its
pseudorandom
output
property
.
The
ef
ficienc
y
and
ef
fecti
v
eness
will
increase
also
by
implementing
these
algorithms
in
its
parallel
v
ersions
as
in
CUD
A
and
e
x
ecuting
them
in
Graphics
Processing
Unit
(GPU).
REFERENCES
[1]
Maya
W
idyastiti,
Amril
Aman,
T
oni
Bakhtiar
.
”Nurses
Scheduling
by
Considering
the
Qualification
using
Inte
ger
Linear
Programming.
TELK
OMNIKA,
V
ol.14,
No.3,
September
2016,
pp.
933
940.
[2]
Ev
en,
S.;
Itai,
A.;
Shamir
,
A.
On
the
Comple
xity
of
T
imetable
and
Multi-Commodit
y
Flo
w
Problems.
In
Pro-
ceedings
of
the
16th
IEEE
Annual
Symposium
on
F
oundations
of
Computer
Science,
Cal
ifornia,
CA,
USA,
1315
October
1975;
pp.
184193.
[3]
Colorni,
Alberto,
Marco
Dorigo,
and
V
ittorio
Maniezzo.
”Genetic
algorithms:
A
ne
w
approach
to
the
timetable
problem.
”
Combinatorial
Optimization.
Springer
Berlin
Heidelber
g,
1992.
235-239.
[4]
Y
uliant
Sibaroni,
Fitriyani,
Fhira
Nhita.
”The
Opti
mal
High
Performance
Computing
Infrastructure
for
Solving
High
Comple
xity
Problem.
”
TELK
OMNIKA
V
ol.14,
No.4,
December
2016,
pp.
1545
1551.
[5]
Fern
´
andez,
Crist
ina,
and
Matilde
Santos.
”A
non-standard
genetic
algorithm
approach
to
sol
v
e
constrained
school
timetabling
problems.
”
In
Computer
Aided
Systems
Theory-EUR
OCAST
2003,
pp.
26-37.
Springer
Berlin
Hei-
delber
g,
2003.
[6]
ˇ
Srndi
ˇ
c,
Nedim,
Emir
P
and
ˇ
zo,
Mirza
Dervise
vi
ˇ
c,
and
Samim
K
onjicija.
”The
application
of
a
parallel
genetic
al-
gorithm
to
timetabling
of
elementary
school
classes:
a
coarse
grained
approach.
”
In
Information,
Communication
and
Automation
T
echnologies,
2009.
ICA
T
2009.
XXII
International
Symposium
on,
pp.
1-5.
IEEE,
2009.
[7]
Chen,
Rue
y-Ma
w
,
and
Hsiao-F
ang
Shih.
”Solving
uni
v
ersity
course
timetabling
problems
using
constriction
par
-
P
ar
allel
Genetic
Algorithms
for
Univer
sity
Sc
heduling
Pr
oblem
(Artan
Berisha)
Evaluation Warning : The document was created with Spire.PDF for Python.
1102
ISSN:
2088-8708
ticle
sw
arm
optimization
with
local
search.
”
Algorithms
6.2
(2013):
227-244.
[8]
Abramson,
Da
vid,
and
J.
Abela.
A
parallel
genetic
algorithm
for
solving
the
school
time-tabling
problem.
Di
vision
of
Information
T
echnology
,
CSIR
O,
1991.
[9]
Fernandes,
Carlos
M.,
Jo
˜
ao
P
aulo
Caldeira,
Fernando
Melicio,
and
Agostinho
C.
Ros
a.
”Ev
olutionary
Algorithm
for
School
T
imetabling.
”
In
GECCO,
p.
1777.
1999.
[10]
Post,
G.,
Ahmadi,
S.,
Daskalaki,
S.,
Kingston,
J.
H.,
K
yng
as,
J.,
Nurmi,
C.,
Ranson,
D.,
Ruizenaar
,
H.
(2008).
An
XML
format
for
benchmarks
in
high
school
timetabling.
In
Proceedings
of
the
7th
international
conference
on
the
practice
and
theory
of
automated
time-tabling
(P
A
T
A
T
2008),
Montreal.
[11]
Di
Stef
ano,
Calogero,
and
Andrea
GB
T
ettamanzi.
”An
e
v
olutionary
algorithm
for
solving
the
school
time-tabling
problem.
”
In
Applications
of
Ev
olutionary
Computing,
pp.
452-462.
Springer
Berlin
Heidelber
g,
2001
A
CKNO
WLEDGEMENT
This
research
w
as
supported
by
Uni
v
ersity
of
Prishtina.
IJECE
V
ol.
7,
No.
2,
April
2017:
1096
–
1102
Evaluation Warning : The document was created with Spire.PDF for Python.