Citation
Analyzing parallel distributed processing models for task schedules

Material Information

Title:
Analyzing parallel distributed processing models for task schedules
Creator:
Edwards, Raviraj
Place of Publication:
Denver, Colo.
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
vi, 69 leaves : ill. ; 29 cm.

Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Electrical Engineering, CU Denver
Degree Disciplines:
Electrical Engineering
Committee Chair:
Wolfe, William J.
Committee Members:
Ross, Douglas A.
Goggin, Shelly D. D.

Subjects

Subjects / Keywords:
Neural networks (Computer science) ( lcsh )
Production scheduling -- Mathematical models ( lcsh )
Neural networks (Computer science) ( fast )
Production scheduling -- Mathematical models ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Thesis:
Thesis (M.S.)--University of Colorado at Denver, 1993.
Bibliography:
Includes bibliographical references.
Thesis:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Electrical Engineering.
General Note:
Department of Electrical Engineering
Statement of Responsibility:
by Raviraj Edwards.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
29150437 ( OCLC )
ocm29150437

Downloads

This item has the following downloads:


Full Text
ANALYZING PARALLEL DISTRIBUTED
PROCESSING MODELS FOR TASK SCHEDULERS
by
Raviraj Edwards
B.S., University of Rhode Island, 1984
A thesis submitted to Hie
Faculty of Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
1993


This thesis for the Master of Science
degree by
Raviraj Edwards
has been approved for the
Department of Electrical Engineering
by
--------f-------
Douglas A. Ross
date


Edwards, Raviraj (M.S., Electrical Engineering)
Analyzing Parallel Distributed Processing Models for Task
Schedulers.
Thesis directed by Associate Professor William J. Wolfe
ABSTRACT
Task Scheduling is an NP complete problem. As an
alternative Macmillan and Chang have suggested Artificial Neural
Networks to solve the scheduling problem. They used a hybrid
neural network of subset -sums and K-clusters to solve the
problem. Here, these PDP models are simulated and their
performances are analyzed.
First, different subset-sum problems are modeled and
compared. One of these subset-sum model is put together with the
K-cluster network to build a scheduler network. A balancing
technique is introduced to balance the two sub-networks. The
scheduler is then used to solve a specific scheduling problem.
This abstract accurately represents the content of the candidate's
thesis. I recommend its publication.
Signed,
hlfe


To Lalina and Jerome
DEDICATION


CONTENTS
CHAPTER
1.INTRODUCTION................................................1
Puipose of the Study................................3
A Task Scheduler: An Example...................... 3
Scope of the Study..................................6
Strategy............................................6
Review of the Literature............................6
Arrangement of the Thesis..........................13
2. SUBSET-SUM NEURAL NET.....................................15
Resources..........................................15
Subset-sum....................................... 15
Problem Formulation................................16
Simulation Results.................................20
Summary............................................25
3. K-CLUSTER NEURAL NET......................................26
Introduction...................................... 26
K-Cluster Connection Weights.......................28
K-Cluster Network Stability Analysis...............29
Results.......................................... 31
4. TASK SCHEDULER.......................................... 32
Introduction.......................................32


VI
Strategy........................................ 34
Problem Description............................... 35
Network Balancing............................. 36
Simulation Results (K=3) Network....................48
Simulation Results (K=5) Network....................50
Simulation Results ¢¢=7) Network.................. 52
Results Discussed...................................55
An Example Scheduler................................55
5. CONCLUSION.................................................59
APPENDIX
A. Scheduler Code Listing......................................61
REFERENCES....................................................68


CHAPTER 1
INTRODUCTION
In today's dynamic society, there is a constant demand for
tasks to be performed. These tasks must be performed promptly
and productively. Although it would be desirable to have unlimited
resources, all resources are finite. It is necessary to manage these
resources efficiently. Effectively allocating resources to tasks is the
function of a task scheduler.
While, ensuring tasks are being completed promptly, it is
important that the task scheduler is maximizing the use of all
available resources. If all available resources are being used at
maximum capacity, the productivity will be high. In other words, if
the sum of the resources being used at any given period of time is
equal to the sum of the available resources^ it is safe to infer that
the tasks are being performed productively. This resource
allocation problem is t3ae classic subset-sum problem where the
subset-sum is equal to the resources available. Despite years of
study^ there are no polynomial-time algorithms to solve the subset-
sum problem [3]. The time to solve a subset-sum problem grows
exponentially with 1iie size of the problem. Often, a non-optimal


2
solution is adequate for most applications, in which only
requirement is that tie solution is nearly optimal and can be
achieved within a reasonable amount of time.
In 1982, Geoffirey Hinton and David E. Rumelhart in [11],
writing with James L. McClelland came up witii a name for a class
of problems they were modeling. They called it Parallel Distributed
Processing ( or PDP). They were using these models to solve
complex problems in a near optimal manner. These models
consisted of large number of simple and similar processors which
were modeled after the neurons in the human brain. There were no
supervisor processors and each processor was sharing the
computation load equally. With the advent of Very Large Scale
Integration (VLSI) circuits, PDP models were easily implementable
and thus became very popular [15]. These models are also known
as Artificial Neural Networks. James M. Macmillan, and Edward
Hok-Lin Chang of University of Colorado have .applied these
models in [9] and [2] to solving the task scheduling problem. They
have suggested further research. This thesis builds on their work
and analyzes the performance of larger and more complex task
scheduling problems.


3
Purpose of the Study
It is best to define the problem first. Task schedulers that are
currently in the field are weak. Almost all of these task schedulers
use priority numbers assigned to tasks to decide which task is next
on line. They do not look at the resource constraints at the time of
scheduling. An active task is executed until a resource it requires is
unavailable. At this time the task is put to sleep (or shelved) and
the next task on line is made active. This type of scheduling results
in lower productivity.
A Task Scheduler: An Example
Task scheduling problems are hard to solve. Task schedulers
that consider availability of resources are known as Resource-
Constrained Schedulers. Job Shop Scheduling i& a class of resource
constrained scheduling and have been studied in [1], [7], [10] and
[4]. Chang in [2], talks about resource constrained schedulers and
has suggested some excellent reference material on early research
in this field. He also points out that until the arrival of neural
networks, the optimization techniques used by the resource
constrained schedulers required large computing power and were
impractical. The reason being that Resource-Constrained
Scheduling problems fall under a well known classical problem
known as Non-deterministic Polynomial Time Complete (NP-


4
Complete) Problem. To date, no one has found an algorithm to
solve these problem in polynomial time.
An example task scheduling problem is explained here as a
frame work for further discussion. In the telecommunication
industry, voice messaging is becoming a common and popular
feature. People call a messaging center to record a message they
want to be delivered. Then via the phone, they specify the time the
message is to be delivered, the destination (phone number), and the
priority of the message. The customer has an option of specifying a
priority number from 1-10. For example, an urgent message could
be identitied as priority 1 as opposed to a non-critical message
which could be identified as priority 10. The user then hangs up the
phone. Prom there on, it is the responsibility of Hie task scheduler
to deliver the message to its destination at the appropriate time.
The message is split into multiple segments at the time of
recording. To play a message segment the digitized voice message
segment should be loaded into cache memory. Instead of loading
one complete message into the cache memory and playing one
message at b time, message segments belonging to different
messages are loaded into the cache memory and played
concurrently. Although different cashed message segments play
concurrently, each segment belongs to a different message and thus
will have a unique destination and will not interfere with the other


segments being played. There are two banks of cache memory
which work alternatively. While one is playing segments of
messages, the other is being loaded with the next segments of
messages. At the next period of time, the banks are switched and
these segments are played. All segments of a message should be
played at consecutive time periods. The following notations will be
used for segments and size of segments:
number of segments for message n = kn
Segment size of message n (Resource required/or Cost)=
Size of Cache Memory (or Target Score) = R Kbits
Total Cashe Memory used (or Score) = S Kbits
At the time of recording, a message can be digitized at
64Kbit^sec, 32Kbit^sec, 16KbiWsec or 8Kbit^/isec. The quality of
the voice being played back is best at 64Kbit^sec and tolerable at
8Kbitg/sec. At the time of recording the customer has a choice.
While the customer is charged less for lower bandwidth the quality
of the message recorded will be lower. All segments are one second
long. This means a message recorded at 64Kbit^sec will have a
segment size of 64Kbits ( 8Kbytes). Similarly a message recorded at
8KbitVsec will have a segment size of SKbits (lKbytes).


6
Scope of the Study
In the last couple of years, artificial neural network task
scheduling models have been studied. These studies have
recommended further research. Here a task scheduler is built and
used to solve a task scheduling problem.
Strategy
The strategy is to build on the results of Macmillan's and
Chang's work in [9] and [2]. A step back is taken to study a few
other models of the subset-sum network. The results are then
compared and the best subset-sum model is chosen. Wolfe and
others have studied the K-cluster network and have reported good
results in [14]. This K-cluster network is combined with the
subset-sum network to form a hybrid network to solve the task
scheduling problem. This network is used on a Centralized Voice
Messaging System to schedule the delivery of voice messages.
Review of the Literature
Notations Used
Vectors are bold lower case letters. Example vectors: a &
b are vectors
* The i^1 element of vector b is bi


7
.Matrices are bold upper case letters. Example W is a matrix.
The element in. the i^1 row and j^1 column is wjj,
Scalars are upper and lower unbolded letters.
Kn is the number of time periods Task n requires for
completion.
rjj is the resource job j requires at time period i.
R is 1ie total amount of resources available to the system. R
stands for available resources.
Sj is the amount of resources used by the system at time
period i. S is sometimes called the score.
W is the weight matrix.
WOO WQ\ - WQn
W\0

*
WmO
wjj is the connection weight from node i to node j.
Artificial Neural Networks
Artificial neural networks, also known as Parallel Distributed
Processing (PDP) models are modeled after our brain. Rumelhart
and Hinton give a frame work for modeling these networks in [8]


8
and [11].The following are some aspects of the network they
describe in detail in this paper:
1. A set of processing units. These units mimic the
neurons.
2. A state of activation. Each unit is in a state of
activation. The activation, corresponds to the excitation of the
neuron.
a{t) -> Pattern of activations at time t.
a{t) -> Activation of unit i at time t.
3. An output function for each unit. This function
relates to the creation of the action potential generated by the
neuron. These action potential travel along the axons.
ait) = /(a()
4. A pattern of connectivity among units. This pattern
is the knowledge base for the network. These correspond to the
axons, the paths along which the action potential travel. This
conveniently represented by a weight matrix W. If wij is non zero,
a connection exists from unit i to unit j.


9
5. A propagation rule. The propagation rule is what
converts the potential arriving on the axon to an input. This
function is performed by the synapses.
net{t) = Wo(i)
6. An activation rule. The function of the activation
rule is to change the state of activation of a neuron depending on
the net input received from the synapses.
a{t) = F{neti{t)) = FQ^waoj)
i
7. A learning rule. This is the method by which the
connection patterns are changed. This corresponds to the growing
of new axons and dendrites. This is also known as the Hebbian
rule and was first introduced by Hebb in [5]. A learning rule will
not be used in this study. Our study concentrates on the
connections and weights required to perform the task scheduling
function.


10
Organizations of the Neural Networks
In a PDP model the activation units are or&anized into
different levels.
Figure 1.Network Organization
Rumelhart and McClelland have organized the network into
three types in [11].They are:
top-down.
bottom-up
interactive
The top-down and bottom-up organizations can be grouped
together as a non-mteractive organizations. In the non-interactive
organization an activation, unit may not interact with a unit more
than one layer away.
The type of organization under consideration, is the
interactive organization, where any unit can interact with any
other unit. Activations can flow in any direction and to any unit,


11
with no layer restrictions. The initial activations of the units
represents the input to the network. The connection weights
represents the knowledge of the network. For the task scheduler
these connection weights represent the type of scheduling. For
example, the resources available (or target score R) and the number
of time slots required to perform a task (K) are represented by the
connection weight. After the network has settled, the initial
activations represents the output of the network.
Interactive Models
The interactive model is the one which will be used for the
task scheduler. Bach unit represents the state of a task at a
specific time period. When the network settles, the final activation
of a unit represents whether a task has been selected for execution
for that time period. Activated units represents selected tasks,
while inactivated units represents tasks that have not been
selected.
Interactive Activation Model
In the interactive activation model, we are interested in the
units which could take on any value in the range [0,1].The units
represent the state of a task at a specific time period. A 0 means


12
the task has not been selected for that time period. A 1 means that
the task has been selected for that time period.
The information sent out by each unit is the product of its
activation and the interconnection weight between the unit and the
unit to which the information is being sent.
The net input is the algebraic sum of the information received
by each units. Let netj be the net input to unit
net] = > awtj

flf (/ +1)=cj( + rj(netj) ; if netj<=
The Energy Function
Netj is a simple calculation which, provides an indication to
increase or decrease the current activation. It is a simple and local
calculation.
The assumption, is that if positive connection weights are
selected the connected units work together. If they are negative,
the units are fighting each other and only one of tiie two units can.
be active at the final state of the network.


13
With the above basic assumption (and wij Wj0 the
activation update ensures that the energy of the network decreases
as the activations are changed.
The activation updates ensures tliat the energy of the network
decreases locally. However it does not ensure that it can reach the
lowest energy of the network.
Local Minima
As explained in the previous section, the activation updates do
not ensure that the network will settle down at the lowest energy.
The network may get stuck in a local minima [15] and never
recover.
Simulated Annealing
A process called simulated annealing has been used to move
the activations out of the local minima. This is a probabilistic
method whica works, but if overdone it can also move the
activations away from the global minima. Simulated annealing is
also discussed in [13].
Arrangement of the Thesis
Chapter 1 introduced the task scheduling problem and
defined the purpose of this study. It discussed a task scheduling


14
problem in detail and outlined the strategy of tiiis study. Finally,
an overview of artificial neural network was given.
Chapter 2 compares different models of subset-sum network.
The models are then simulated and from the results of the
simulation one model is chosen for solving the task scheduling
problem.
Chapter 3 discusses the work that has been done on the K
cluster network and explains in detail how this network is modeled.
Chapter 4 brings together the subset-sum and the K-cluster
network models to solve Hie task scheduling problem. The results of
the scheduler are discussed in depth.
Chapter 5 uses the task scheduler on a few task scheduling
problems. The results are discussed here.


CHAPTER 2
SUBSET-SUM NEURAL NET
Resources
Resources are the limiting factor for scheduling tasks. A task can be
scheduled only if all the resources required by that task are available. If a
task requires few resources, it may be possible to schedule another task
along with it. When multiple tasks are being scheduled for the same period
of time, the constraint is that the sum of the resources being used by these
tasks should be less than or equal to tiie amount of resources available for
that time period.
A task scheduler requires a component which assures that the total
amount of resources required by the scheduled tasks are less than the
resources available. This is the Subset-sum component of the task scheduler.
Subset-sum
The subset-sum problem poses an optimization problem. If C={ciC2,
C3....Cn) is a set of positive numbers whose sum is T, find a subset of C
whose sum is R.
The subset-sum problem is a simplified 0-1 knapsack problem. In the
0-1 knapsack problem, a thief has a choice of selecting from a set of items
X={xi,X2, X3...xn}whose values are V={vi,V2, V3...vn} and sizes are
S={sj, S2, S3..sn}4 The only limitation the thief has is the size of a


16
knapsack. If the size of the knapsack is R, which items of X={xj, x£,
X3....xn} will the thief chose to maximize the value of the stolen goods. The
knapsack problem becomes a subset-sum problem if the value V is directly
proportional to the size S.
Problem Formulation
In our example task scheduling problem, the amount of cache memory
required by a task can be considered to be C Kbytes ={ciC2, C3.c^}, The
cache memory available to the Centralized Voice Messaging system is R
Kbjrtes. Task n requires Kbytes of cache memory. The task scheduler
should select tasks, so that the sum of the cache memory required by the
selected task is approximately equal to R Kbjrtes.
For the subset-sum problem each task is mapped to a single processing
element (or neuron). This processing element is referred to as a node. A task
is selected if its node is on (or activated) when the network reaches a steady
state. If it is off, the task is not selected. Four different models of subset-sum
neural nets were considered. The first was the simplest and the fourth the
most complex.
Subset-sum 1
Each node is connected to every other node with a connection weight of
the negated cost of the other node (-Cj^). This means that the net input to
each node is the sum of the cost of the active nodes. If the external
connection to each node is iiie target score (R), Uie node compares the target
score with its net input and adjusts its activation accordingly. If the net


17
input is less than the target score (R), the node tends to activate itself. If the
net input is higher tiaix the target score, the node tends to de-activate itself.
Each node is adjusting its activation to satisfy the subset-sum constraint.
This process is being done concurrently at each node. When the network
runs to completion, it is expected that the sum of the cost of all active nodes
equals the target score at each node. The following diagram shows this
network:
Figure 2. Subset-sum 1 Network Model
Subset-sum 2
The connection weights of the first network were not symmetric. This
network builds on. the first network in order to make it symmetric.
The connection weights were made symmetric by setting them to -
(Cj^Cjc). This change made it necessary to set the external input to R*Cj. (It
can be easily seen tiiat Cj can be factored out from the net input.)


Figure 3. Subset-sum 2 Network Model
Subset-sum 2
The third network was from the work done by Wolfe and others in [1*7
The value for ALPHA was selected to be 0.5. This network is referred to as
the BASE model for the Subset-sum problem.
Figure 4. Subset-sum 3 Network Model


19
Subset-sum 4
While running some simulations of subset-sum 3 network, it was noted
that this network could be improved by adding a constant value to the
external input. Different values were tried for this constant. A value of 0.05
gave the best results.
This network is identical to subset-sum 3 network except for tiie
modification to the external input.
Figure 5. Subset-sum 4 Network Model
Subset-sum 5
This network is from the work done by Wolfe and others in [17]. I
came across this network at the latter stages of this study. Some simulations
were run to compare the results with the previous 4 types of the network.


20
Figure 6. Subset-sum 5 Network Model
Simulation Results
Many 15 node simulation runs were made on each type of the above
Subset-sum network. The target score (R) was always 1.The task costs for
each run were randomly initialized and then normalized to 1.The initial
activation, for each node was randomly initialized to a very small number.
For each run, Uie percentage error of the score was calculated. The
runs were grouped into ranges of percentage errors. The ranges were
increments of five. The following charts summarize the results by showing
the proportion of percentage errors for each network.


21
*A error VS % runs
SubMtcum 1 network
90 j
80 -
70
60
0 15-10] [10-16] 16-20] [20-2S] [2640] [30-36] [36-40] [4045]
% error ranges
Figure 7. Subset-sum 1 Network Results


22
%error VS % runs
Subset-sum 2 network
_ IB 0111 _
[0-6] [fi-10] [10-16] 11640 [20-25] [25-30] p-35] [36-40] 14045]
% error range
0^00^0000
9876a4)r* 21
Figure 8. Subset-sum 2 Network Results


23
% error VS % runs
Subset_sum 3 n^wcilc
90 j
-
70 _
60 --
60 -
s
40 -
l-Bl [S-1l [10-1S] [15-20] [20-25]
% error range
Figure 9. Subset-sum 3 Network Results


24
% error VS S runs
Subset-sum 4 network
Figure 10. Subset-sum 4 Network Results


25
90 x
% %uor VS % runs
Subset-sum S network
Figure 11.Subset-sum 5 Network Results
Summary
The results of the simulations suggest that the subset-sum 4 network
performed better than the first three. This network was chosen to build the
task scheduler network. The subset-sum 5 network also performed well.
Prior to this study this network was analyzed by Wolfe and others in [17]
yielding the same type of results.


CHAPTER 3
K-CLUSTER NEURAL NET
Introduction
The K-cluster network has been studied in detail by Wolfe and others
in. [17], and have reported good results with this network. This K-cluster
network (without any modiHcations) is used to build the task scheduler
analyzed in this thesis. Most of the information presented here are from the
class notes [16] and the publication [17].
K-cluster networks selects K winners with an additional criteria that
the selected winners are clustered together. Tlie network can be viewed as
selecting an N-cube comer with K number of l's and that the l's are
clustered together (wrap around clustering is allowed). N-cube or Brain
State in a Box model was developed by J.A. Anderson (1977)[11]).The
following is a 3-cube model depicting a 2-cluster 3 node network.


27



The K-cluster network settles on one of the 3 2-cluster comers (marked
by a dots). Unfortunately with wrap around clustering, the 3-cube 2-cluster
comers are tiie same as the 2-winner comers. Since it is impossible to draw
a 4-cube in a 2 dimensional space, a graphical representation of a 4 cube is
not attempted here.
Although all K-cluster comers are considered feasible solutions, not all
of these corners are optimal solution. In [17] the definition of Hie optimal
solution of the K-cluster state corresponds to the largest area under the
graph of the initial activation's. This is shown, in the following diagram.
8-c]istr 13 nod natwork


28
K-Cluster Connection Weights
In [17], the K-cluster network is defined as a Hopfield-style [6] network
with an additional property that each unit sees the same distribution of
connection weight. This implies that if one row of the connection weight
matrix W is known, all other rows of W can be easily obtained by shifting the
known row circularly. In [16] and[17], it is shown that this property reduces
the net input to a simple discrete circular convolution of row 1 of the weight
matrix W with activation vector a.
Wy =
if S(iJ) < (k-l)/2
otherwise
where ^(i, j) is the minimum distance between
the indices i and j.


29
W
0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0
0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 0 0 0 -1 -1 -1 1 -1 -1 -1 -1
-1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1
-1 -1 -l -1 0 0 0 0 0 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1
-1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 1
-1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1
-1-1-1-1-1-1-1-10 00 0 0
0 11111111 0 0 0 0
0 0 -1-I -1-1-1-1-1-1 0 0 0
neti > jWij^+ei
Since the rows of the connection matrix W are shifted versions
of row 1,the net input can be found by convolving row 1 of W
with the activations. This is explained clearly in [17].
K-Chister Network Stability Analysis
The stability analysis allows us to determine a value for the external
inputs, so that k states are stable for a given K. With iateractive activation
updates, it can be easily seen that a comer state is stable if the net input to


30
the active units are positive and the net inputs to the inactive units are
negative.
-l Jnefc(t) [l-a(t)] ifneti S 0
a( ) a() 7?|n_ ] ifneti(t) >
The comer states are stable if,
1 a(t)=1 and neti(t) ^ 0
and 2. a=0 and net < 0
The net input to the inactive unit at the edge of the cluster is :
neti = (k ((k-l)/2))*(-l)+ e < 0
i.e. e < (k+l)/2
Similarly the net input to the active unit at the edge of the cluster is:
net = ( k -1-((k-l)/2))*(-l)+ e > 0
i.e. e ^ (k-l)/2
From the above two conditions, a K-cluster network will be stable only if
the external input e satisfies the following condition:


31
(k-l)/2 £ e < (k + l)/2
Results
Several k-cluster networks were simulated jdelding positive results. In
[17], the network has been observed to be stable and 100% of the solutions
were observed to be feasible solutions. 50% of solutions were found to be
optimal, it is also noted in [17] that many of the non-optimal solutions were
close to the optimal solutions.


CHAPTER 4
TASK SCHEDULER
Introduction
This chapter analyzes the task scheduling problems investigated by
Macmillan in [9] and Chang in [2] in more detail. Macmillan, combined the
subset-sum network and the K-cluster network to build a non-preemptive
task scheduling network. Similar to Macmillan's network, to build a
preemptive task scheduler a K-winner network could be used instead of the
K-cluster network. This study concentrates on the non-preemptive task
scheduling problem only.
C
1~u~U~Ur ~LJ~LJ~U~LJ~LJ~LJ~LJ~LI~I
( ^ l_l 1 ~ ~ ~ | | j 1 _n n 1 K*Ciitr Nstwet
!
!
r
:an
Sub network to prf6rrK4 V4l
Figure 12. Task Scheduler Network Layout


33
The layout of the task scheduler network is shown in Fig.1.The
subset-sum and K-cluster networks, discussed in Chapters 2 and 3, are sub-
networks of the task scheduler network. The subset-sum sub-network runs
vertically (column oriented) and the K-cluster sub-network runs horizontally
(row oriented). The connection weights are not shown for clarity of the
diagram. Each row represents a task and each column represents a time slot
(or time period).
The cost of each task is represented in the connection, weight of the
subset-sum sub-network. Similarly, the time period required to complete a
task is represented by K in the K-cluster network. Each row (i.e. each task )
could have a different value for K but in our study here K will be the same
for each row.
In our Voice Messaging example, K identiHes the length of the message
in seconds. The cost of each taslc represents the bandwidth at which that
message was recorded. Higher bandwidth costs more (cache memory) and
lower bandwidth will cost less ( cache memory).
The resources available at each of the time slots are represented by the
external inputs to the nodes. This is the cost the task scheduler schedules
around. If the tasks are scheduled such that the total cost of each time slot is
equal to the cost of available resources, the tasks execute efficiently. If the
cost of the scheduled tasks exceeds the available resource the schedule
becomes an invalid schedule. It is important to note here, that our scheduler
provides us an approximate solution and that the total cost need not be
exactly equal to the cost of available resource but within the proximity of it.


34
Lastly, the preference of a time slot for each task is represented by the
initial activation (or the Preference Value) of the node. If the node,
represented by row a and column b is initialized to a high value, the
preference for task a to be performed at time slot b is also high.
Strategy
The task scheduling network is built by integrating the subset-sum
network discussed in Chapter 2 with the K-cluster network discussed in
Chapter 3. Each of these networks are referred to as sub-networks.
The integration of the two sub-networks produces undesirable effects on
the performance of each individual sub-network. It seems that the
performance of one sub-network negatively affects the strength of the other
sub-network. In order to reduce this negative effect on the performance of
the scheduler, the strengths of the two sub-networks should be balanced.
The balancing of the two sub-networks are achieved by introducing a
Balancing Constant to the subset-sum sub-network. The Balancing
Constant scales the connection weights of tiie subset-sum network.
The performance of the scheduler network is analyzed by changing the
Balancing Constant. The performances of the network are compared and the
best Balancing Constant is selected. Finally, simulations are run with
balanced and unbalanced scheduler networks and the results discussed.


35
Problem Description
The task scheduling problem described earlier may be defined as
follows:
Given a finite set S = [s\ sz
consisting of n elements

and V
Vll V12
V21..
Vim
Vnl Vn2 Vnm
n
where ^Si = N
and a tzxget t < N
find a matrix A
an an aim
021...........
Oil......Cbm
where ay =1 or 0 {the 15 are clusterd together)
n
such that t {for each f)
i =1
m
and ^aa = K for each j
m
and is maximized for each


36
The m*n matrix A is the result produced by the task scheduler. Each
row of matrix A represents a task being scheduled. There are 'n' rows
representing 'n' tasks. A time slot or a time period is represented by a single
column in A. If a^j is one, task i has been selected for execution at time slot j.
If it is zero, task i has not been selected for execution at time slot j.
Consider the vector S, to be the cost vector for the tasks. The cost of
executing task i during a time slot period is sj. The condition
n
^Si*aj t maximizes the cost at each time slot. The cost of
i =1
executing the selected task is approximately t.
m
The condition =k ensures that each task is scheduled for
only K time slots. The condition that Is in ajj are clustered in each row
ensures that the tasks are scheduled non-preemptive.
Finally, the matrix V is the preference value for executing a task. If vy
is high, the task i has high preference to be executed at time slot j and vice
m
versa. The concnuon to maximize ^ Vt, *a ensures that the preference
values for each task is maximized.
Network Balancing
After many simulations of the scheduler network, it was concluded that
the performance of the network was not acceptable. The row oriented K
cluster sub-network and the column oriented subset-sum sub-network were


37
negatively affecting each other. When the K cluster sub-network was
stronger than the subset-sum sub-network, the resultant scores for each time
slot were off by a large amount. It seemed that Uie ejects of the subset-sum
network were being ignored. When the subset-sum sub-network was
stronger, the resultant network performed poorly in picking a K cluster. TTae
selected time slots were either not clustered together or they did not sum up
to the expected value of K.
The following are some examples of an unbalanced network.


Neural Network:10 Jabs 10 Time Slots K 3
Task Costs: 0.04 0.05 0.05 0.06 0.07 0.10 0.15 0^0 0.Z3 0.33
Scares : 0.7 0.7 0.7 OJ 0*3 02 02 CU 03
An Unbalanced Task scheduler
o


T
a o
s
K o o
s
_

Tims Slots ->
U3
CD


Neural Network:10 Jobs IS Tone Slots K* 7
Task Costs: 0.04 0.05 QilS 0.06 0.07 0.10 0.15 O.ZO 0^3 0.33
Scores 0^ 0.9 03 03 OJ 0.3 Q3 0^ OJ 0^ OJ 0.3 QJ3 QJ OS
An Unbalanced Task scheduler
........
........
........
T .........
* .........
k .......
s .........
........

Time Slots --
U)
VO


Neural Network:10 Jobs 40 Time Slots K9
TasK Losts 0.04 0.05 0.05 0.06 0.07 0.10 0.15 0.20 0.Z3 0.33
Scores : OJ 0.5 0.5 D.S 0.5 0.S 00 00 0.0 0.3 OJ OJ 0.3 0.3 0.0 00 0.0 0.4 0.4 0.4 0.4 0.4 0_4 0.4 0.4 0*4 0.0 0.0 0.0 0>3 03 0^3 DJ 0.0 0.0 00 0 An Unbalanced Task scheduler



T
a
s
k
s



' * *
1 * *
'* ' '











Time Slots------>
x>


41
In order to balance the network, a Balancing Constant was added to the
sub set-sum sub-network. There were two ways of using this balancing
constant. Both these methods were tried out, however the second method
performed better. The second method was utilized for the simulations results
shown in this study.
The first method was to scale the net input to a node at each iteration
of the network. The net input to a node was differentiated as one contributed
by the sub-set sum part of the network and the other contributed by the K-
cluster part of the network. The balancing constant was used as a scaling
factor to the net input from the sub-set sum network.
net_inputsch,A>ur = (BC net_inputsuutt_,m ) + net_inputK_duster This method
distorted the performance of the subset-sum sub-network considerably.
The second method was to scale the normalized task costs and the
target score at the initialization of the network. This enabled the network to
run without differentiating the net inputs from the two different types of sub-
networks. Secondly, this method did not distort lie affects of the subset-sum
network as much as in method 1.
The results of the scheduler network was plotted for different values of
the Balancing Constant ranging from 0.1 to 0.5.
The network was initialized with preference values and run with
random costs for the tasks. The score (scheduled cost) for each time was
calculated. The highest score was determined and averaged over 25 runs.
This averaged highest score is labeled as the Maximum Average Score.


42
In the following charts, the network Maximum Average Score is plotted
as the independent variable and the Balancing Constant dependent variable.
10*10 network K = 2
Average Max Error in Score VS Balancing Constant
10*20 network K = 3
Average Max Error in Score VS Balancing Constant


10*30 network K 5 3
Average Max Error in Score VS Balancing Constant
10*40 network K = 2
Average Max Error (n Score VS Balancing Constant
Balancing Constant


44
10*10 network K =5
Average Max Error In Score VS Balancing Constant
10*20 network K = 5
Average Max Error In Score VS Balancing Constant


10*30 network K = 5
Average Max Error in Score VS Balancing Constant
Balancing Constant
10*40 network K = 5
Average Max Error in Score VS Balancing Constant
Balancing Constant


46
10*10 network K = 7
Average Max Error in Score VS Balancing Con^ant
10*20 network K = 7
Average Max Error in Score VS Balancing Constant


47
10*30 network K = 7
Average Max Error in Scorn VS Balancing Constant
10*40 network K 5 2
Average Max Error In Score VS Balancing Constant


48
Simulation Results (K=3) Network
A 10*10 Unbalanced Network BC =1.0
runs
A 10*10 Balanced Network BC = L3
03$S25S1 4703692 314703692581470


49
10*20. Unbalanced Network EC =
In Uiis case the results seems to be good, but the scheduler failed to
cluster the time slots.
runs
10*20 Balanced Network BC = 0.75
In order to improve the performance of the K cluster network the
subset-sum network was weakened. This was done by selecting a balancing
constant less than 1.0. Here a balancing constant of 0.8 is chosen. At the
cost of a 15% score error the performance of the network was improved.


runs
Simulation Results (K=5) Network
10*10 Unbalanced Network BQ =lil


51
Max Score Error
10*10 Network K3
Unbalanced
Ideal Satisfaction
-Scheduled
satisfaction
-Max Score Error

22233344446666667777898999
p3e926814703926147036926B147
mns
10 10 Balanced NetwoA BC = 1.4
5
L
II
c
B
-
ork
N<
d
e
c
n
B
n
Ba
o
*
o


52
Simulation Results Network
10*10 Unbalanced Network BC =1.0
10* IQ Balanced Network BC = JL5


53
10*20 Unbalanced Network BC =1.0
6 9 2 5 6
0 3 6 9 2 6 8
6 9 2
10*20 Balanced Network BC =1.3
runs


54
10*30 Unbalanced Network BC = 1.0
10*40 Unbalanced Network BC =1.0
036925814703692 ¢814703892681470
0
runs


55
Results Discussed
The Average Maximum Error in Score vs. Balancing Constant charts
show that as the subset-sum sub-network increases in strength the score
errors decrease. This does not mean that a high Balancing Constant
improves the performance of the scheduler. The performance of the
scheduler depends also on the strength of the K-cluster sub-network. When
the K-cluster sub-network is weak, the K-clustering property of the network
is lost. Some-times the scheduled time slots were not scheduled and other
times the number of scheduled time slots were not equal to K.
These results imply that there must be a trade off between the accuracy
of the target score and the clustering property. In the simulations here, the
trade off was approximately 15% of the target score in order to keep the K-
clustering property. The scheduler performed better when they were
balanced. An unbalanced scheduler performed poorly.
Example Scheduler
In this section, the balanced task scheduler network was used as a
scheduler for the Voice Messaging system explained in the Chapters 1 and 2.
The cost vectors were set to be proportional to the bandwidth of the voice
recording. The Bandwidth costs of 64Kt/sec, 32Kfc/sec and 8Kb/sec were set


56
to 1,0, 0.5 and 0.25 respectively. Unfortunately, the normalizing of the cost
vectors distorted the cost ratios a little.
The 10*40 scheduler was initialized to schedule for 10 voice lines for a
time period of 40 seconds. The network parameters were initialized the
following way:
The bandwidths for the voice segments were randomly
generated.
The length of the voice segment indicated by the value of K
in the K-cluster network was set to 5.
The time at which a voice segment was to be played was
indicated by giving a preference value for that time slot. This time period
was generated randomly. Twenty continuous time slots, beginning at a
randomly generated time, were set as preferred for each of the 10 voice lines.
This implied that a delay of 20 seconds for a voice response was acceptable.
The preference values were initialized to 0.01.
The maximum cost allowed per time slot was set to 1.0.
This is referred to as the score.
The best schedule for tiie above example produces a scheduler reward of
0.5 ( = 5 0.01 10) while the cost of the schedule for each of the 40 time
slots should not exceed the score (1.0).
The ideal reward, the scheduler reward and the maximum cost error
indicate the performance of scheduler. For an optimal solution, the scheduler
reward should be 0.5 and the maximum cost error should be 0.


57
The following graph is the results of the scheduler. It shows that the
scheduler performed near optimal preference of 0,5. There were some
optimal solutions. The spikes on the graph indicates that for some runs the
cost error exceeded the available cost. The maximum cost error was
approximately 17%,
2*e
2
1.6
0.6
0
10*40 Network K=5
An Example
Ideal Satisfaction
Scheduled
satisfaction
Max Score Error
A
Max Score Error
13$ 91112223933444666806677788 80989
258147036926814709 92581470369
runs
The following charts show the results of the scheduler. The rows
represent the 10 tasks (or voice lines). The columns are the 40 time slots the
scheduler uses for scheduling. Each column represents 1 second of voice
segment. A square box indicates a preference value assigned for that time
slot. Each tasks was initialized to have 20 contiguous preferred time slots.
The number of segments played was represented by K in the K-cluster sub-
network. These segments are required to be contiguous. The value of K was
set to 5 for each task. The black dots in the diagram represent the final
result of the scheduler. These are the time slots the scheduler picked for the


58
Figure 13. Scheduler Example 1.
tasks. The result should be such that the black dots are contiguous and they
are all inside the square boxes.
c UEU u

DBes
DOS 0
s SD
DOB 0
e s 0
H
. B

ffl o
a @

o ffi
o ffi n

n



1 sm
""s
^ B
^ so
SB
^ s
^ OS
_ ffi
s

no
D-'a
S-B
|
Is
Is s
-
n

n
s n
E n
San
n
B
ra
o w
ra
ra
n
n

n







s
s

s










s
0

0
B
Q
s







0


o



I s
I

o
E
B
s

o o

pp


0
Q
s
s





0


0
s
B
B
s



0

o





s
s
s
0
a s
o



n
n
n
c
c

n
n
ra
m

n


o
o




09
s

0
@
on

n
a
0 0

s
&

0
E








Figure 14. Scheduler Example 2.


CHAPTERS
CONCLUSION
Although the task scheduler network did not produce optimal outcomes,
the solutions for the most part were feasible and within the proximity of the
optimal solutions. On some occasions the solutions were not feasible
solutions. For example, when the subset-sum sub-network was stronger
than the K-cluster network, it was observed, that the clustering property of
the network was being ignored by tihe network. This was because the
stronger subset-sum sub-network was working harder to satisfy its
constraints and thereby overpowering the k-cluster sub-network.
The important observation from this study is that it is necessary that
the two sub-networks are balanced. The balancing is very difficult to
accomplish, especially when the network initialization parameters are
different for each schedule. In this study the preference values (or the initial
activations) of the tasks were stable while the costs were being changed for
each schedule. The maximum average error for each schedule was plotted for
various values of a network balancing constant. The balancing constant at
which the maximum average error became zero was the point at which
subset-sum sub-network over powered the k-cluster sub-network. Hie
balancing constant that produced a maximum average error of 15% produced
feasible solutions which were close to the optimal solutions.


60
The performance of the scheduler network moves towards optimal
performance when a high number of tasks are being scheduled. The reason
being, tJie subset-sum sub network has a bigger pool of tasks to select from
and thereby work with the nodes selected by the k-cluster sub-network
instead of working against it. This allows the two sub-networks to work
together.
As general purpose schedulers the PDP models of task schedulers do not
perform well. But for specialized types of task scheduling, where the initial
parameters are within a known range and the Bolutions are not constrained
to be optimal, the PDP model performs adequately.


APPENDIX A. Scheduler Code Listing
The scheduler: Row are K Cluster sub-networks
Column are subset-sum sub-networks
* Code used for simulating the scheduler for the
Voice messaging problem.
..................................********.........7
#include
#include
#include
#include
/
* Define Constants used.
7 ,
#define ITERATIONS 750
#define JOBS 10 /* this is the maximum number ot jods */
#define TIMESLOTS 40 /* this is the maximum number of Time
slots V
#define MAXA 1.0
#define MINA 0.0
#defme SUBSET.CONST 2.0 r should be 2.0 normally */
#defin.e BC 0.95 /* Balancing constant for the sub-networks V
r
* Global variables used.
V
extern Display *theDisplay;
intKLUSTER[JOBS];
int klust = 5;
float STEP_SIZE = 0.1;
float SAVE_SIZE;
int ra viscount =0;
int scheduler( theWindow)
Wmaow the Window;
float initial_a[TIMESLOTS][JOBS];


62
float ia_save[TIMESLOTS][JOBS3;
float a[TIMESLOTS][JOBS];
float a_save[TIMESLOTS][JOBS];
float netjTIMESLOTS][JOBS];
float normaUength, score, sum;
mt i, j, k,l,m, n, gx, gy, draw_size[2], nodes, time, offset;
char string[256i, tstr[32], scheduled_str[256];
FILE 1;
int column;
int distance;
float rscore[TEMESLOTS], s[TIMESLOTS];
float ALPHA;
float penalty_factor[TEMESLOTS] [JOBS];
float ascore [TIMESLOTS];
float max_cost_error, total_score, max_reward, reward;
float column_cost, column_cost_error;
nodes = JOBS;
time = TIMESLOTS;
score =1.0;
ALPHA = 0.5:
/* num of tasks to be scheduled /
/* num of time slots used by sc&eduler V
r A constant used by the subset part */
* Open a file for outout
V
if( (fpl=fopen("example.doc,,J "a") ) == NULL ){
printf("\nError Opening file\n");
return
/
* Init time slots required for each tasks
V
for (i = 0; i < nodes; i++ ) {
KLUSTER[i] = kiust;
* Initialize Activations: Connection weights for SUBSET problem.
* Randomly at 0.25,0.50,0.75 Or 1.0


63
7
for(i=0, normaljengtih = 0; i< nodes; i++) {
initial_a[0][i] = ((float) (rand%4 +1))* 0.25 ;
normaUenglh += (initial_a[0[i] initiala[0][i]);
}
/
* Normalize the connection weights (ie. the costs)
V
normalength = (float)sqrt((double)normal_length);
for(i=0; i< nodes; i++) {
initxal_a[0] [i] /= normal_length;
r
* Balance the subset network by BC
V
for(i=0; i< nodes; i++) {
initial_a[0][i] *= BC;
ia_save[0][i] = initial_a[0][i];
}
score *= BC;
r
* Initialize tiie preference values
V
for(j = 0; j < time; j++) {
for ( i = 0; i < nodes; i++ ) {
aD][i] = 0.0;
a_save[j][i] = 0.0;
r
* For each job randomly initialize 20 preference slots,
* and preference value of 1.
V
max_reward = 0.0;
for (i = 0; i < nodes; i++ ) {
j = rand%time;
= 0.01;
a[+l)%time][i] 0.01;
a[G+2)%time][i] : 0.01;


64
a[G+3)%time][i] = 0.01;
a[G+4)%timej[i] = 0.01;
a[+5)/otime][i] 0.01;
= 0.01;
a[G+7)%time][i] = 0.01;
a[+8)%time][i] = 0.01;
a[+9)%time][i] =0.01;
a[G+10)/otime][i] = 0.01;
a[(j+ll)%time][i] =0.01;
a[(j+12)/otime][i] = 0.01;
a['+13)%time][i] = 0.01;
a[+14)%time][i] = 0.01;
a[+15)%time][i] = 0.01;
a[+16)%time][i] = 0.01;
a[+17)%time][i] = 0.01;
a[+18)%time][i] = 0.01;
a[+19)%time][i] : 0.01;
max_reward += 0.05;
a_save[j][i] = 0.01;
a_save[+l)%time][i] = 0.01;
a_save[(j+2)%time][i] = 0.01;
a_save[(j+3)%time][i] =0.01;
a_save[(j+4)%time][i] = 0.01;
a_save[(j+5)%time][i] = 0.01;
a_save[+6)%time][i] = 0.01;
a_save[(j+7)%time][i] = 0.01;
a_save[(j+8)%time][i] = 0.01;
a_save[+9)%tiine][i] = 0.01;
a_save[+10)%time][i] = 0.01;
a_save[(j+ll)%time][i] = 0.01;
a_save[(j+12)%time][i] = 0.01;
a_save[(j+13)%time][i] = 0.01;
a_save[+14)%time][i] = 0.01;
a_sa timei[ij = 0.01;
a_sa time]i] = 0.01;
a_save[+17)%time][i] = 0.01;
a_save[(j+18)%time][i] =0.01;
a_save[(j+19)%time][i] = 0.01;
Update the costs for the rest of the columns


65
V
for (i = 0; i < nodes; i++) {
for(k =1;k < time; k++ ) ia_save[k][i] = initial_a[k][i]
initiaa[0][i];
* Iterate the Neural Net
V
for (i = 0; i < ITERATIONS; i++ ) {
/ initialize nets to zero */
for(1=0;1 < time;1++) {
for =0; j r
* calclulate net input K-cluster part
V
for (1=0;1 < nodes ;1++ ) {
r
calculate net input for each activations
V
for (m = 0; m < time; m++) {
for (k = 0; k < time; k++) {
if(( ((m-k + time)%time) < ((k-m + time)%time)))distance = (m-
k+time)%time;
else distance = (k-m +time)/otime;
if( distance > (KLUSTER[l]/2)) {
net[m][l]-=((a[kKl]));
net[m][l]+= ((((float)KLUSTER[l]V2.0;
r
* Calculate the net input for the subset part
V
for = 0;1 < time;1++ ) {
for (j = 0; j < nodes; j++) {


66
for (k = 0; k < nodes; k++) {
if!=k) {
net[l][j] -= ((a[l][k] (((SUBSET.CONST* initial_a[l][k]) *
(initial_a[l]|j])))));
net[l][jJ+= ((02.0*score) ALPHA) (initial-a[l][j));
net[l][j] += 0.05;
r
* Update activations
/
for (m = 0 ; m < time; m++) {
for =0; j < nodes; j++ ) {
alm][j]=(
netm][j] >= ) ? (a[m[j] + (STEPSIZE* ( net[m[j]*( MAXA -
a[m]B])):.
(a(m][j] + (STEP_SIZE*(net[m][j]*(a[m][j3 -MINA))));
net[m][)] = 0.0; /* clear net for next iteration use */
/
* Calculate reward for schedule
7
reward = 0.0;
for (i = 0; i < nodes; i++ ) {
for G = j < time; j++ ) {
if(a[j][i]>.6){
reward += a_save[j[i
if(a[+l)%time][i] > 0.6)reward += a_save][i]
if(a[+2)%time][i] > 0.6)reward += a_save[j][i]
if(a[+3)%time][i] > 0.6)reward +- a_save[j][i]
if(a[+4)%time][i] > 0.6)reward += a_save[j][i]
break;


67
r
* Calculate Max error
max_cost_error = 0.0;
for G = 0; j < time; j++ ) {
column_cost 0.0;
for(i = 0; i < nodes; i++) {
if(a[j][i] > 0.6)column cost += ia_save[j][ih
}
if ( co!umn_cost > score) {
colmnn_cost_error = column_cost -score;
if( column_cost_error > max_cost_error) max_cost_error =
columncosterror;
printf("\n%d: Max Rewards = %1.5f Scheduler Reward = %1.5f Cost
err = %1.5f',
++ravi_count,max_reward, reward,
(max_cost_error/score) 100.0);
fprintf(fpl,"\n%1.5f\W4>1.5f\t%1.5f,, max_reward, reward,
(max_cost_erroi/score) 100.0
fclose(fpl);


REFERENCES
[1] J. Barker and G. B. McMahon, "Scheduling for General Job Shop,"
Managemeat Science. May 1985.
[2] Edward Hok-Lin Chang, "Neural Network Approach to Resource
Constrained Scheduling," Master's thesis, University of Colorado at
Denver, 1992.
[3] Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest,
Introduction to Algorithms, The MIT Press, 1990.
[4] W. S. Gere, "Heuristic in Job.Scheduling," Management Science. Nov.
1966.
[5] D. O. Hebb, Edited by J. A* Anderson and E. Rosenfeld, "The
Organization of behavior," Neurocomputing: Foundation and
Research, 1943.
[6] J. J. Hopfield, "Neural Networks and Physical Systems with Emergent
Collective Computational Abilities," Proceedings of the National
Academy of Science, 1982.
[7] J. 6. Lassere, "An Integrated Model for Job-Shop Planning and
Scheduling," Management Science. 1992.
[8] Richard P. Lippmann, MAn Introduction to Computing with Neural
Nets," IFiRE ASSP Magazine, April, 1987.


69
19 James M. Macmillan/SoIving the Task Scheduling Problem using
Neural Networks," Master's thesis, University of Colorado-Denver,
1989.
[10] J. Carlier and E. Pinson, "An Algorithm for solving the Job-Shop
Problem," Management Science. Feb. 1989.
[11 D.E. Rumelhart and G.E. Hinton, "A General Framework for Parallel
Distributed Processing/ Parallel Distributed Processing: Exploration
in the Micro Sructure of Cognition, Volume 1,The MIT Press, 1989.
[12] J. A. Shaw, "Solving Optimization Problems using the Recurrent
Neural Networks," Master's thesis, University of Colorado at Denver
1991.
[13] H. Szu, "Fast Simulated Annealing,*' AIP Conference on Neural
Networks for Computing,1986.
[14] W. J. Wolfe, et aL "K Winner Networks," IEEE Transactions on
Neural Networks, Jan. 1991.
[15] W. J. Wolfe, "Introduction to Neural Networks," Class Notes Part I,
University of Colorado at Denver. Summer 1991
[16] W. J. Wolfe, "Introduction to Neural Networks," Class Notes Part II,
University of Colorado at Denver, 1991.
[17] W. J. Wolfe, et al."Homogeneous Networks," Manuscript, University
of Colorado at Denver, May 1992.
[18] W. J. Wolfe, et al. "Inhibitory Grids and the Assignment Problem,1
TPiFST*! Transactions on Neural Networks, March 1993.




Full Text

PAGE 1

ANALyziNG PARALLEL DISTRffiUTED PROCESSING MODELS FOR TASK SCHEDULERS by Raviraj Edwards B.S., University of Rhode Island, 1984 A thesis submitted to the Faculty of Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 1993 .. .. :('.'\ j" ...

PAGE 2

This thesis for the Master of Science degree by Raviraj Edwards has been approved for the Department of Electrical Engineering by Douglas A. Ross Shelly D. D. Goggni date

PAGE 3

Edwards, Raviraj (M.S., Electrical Engineering) Analyzing Parallel Distributed Processing Models for Task Schedulers. Thesis directed by Associate Professor William J. Wolfe ABSTRACT Task Scheduling is an NP complete problem. As an alternative Macmillan and Chang have suggested Artificial Neural Networks to solve the scheduling problem. They used a hybrid neural network of subset -sums and K-clusters to solve the problem. Here, these PDP models are simulated and their performances are analyzed First, different subset-sum problems are modeled and compared .. One of these subset-sum model is put together with the K-cluster network to build a scheduler network. A balancing technique is introduced to balance the two sub-networks. The scheduler is then used to solve a specific scheduling problem. This abstract accurately represents the content of the candidate's thesis. I recommend its publication.

PAGE 4

DEDICATION To Lalina and Jerome

PAGE 5

CONTENTS CHAPrER 1. INTRODUCTION ........................................................................................ 1 Purpose of the Study ..................................................................... 3 A Task Scheduler: An Example .................................................... 3 Scope of fue S'tu.dy ...................................................................... 6 Strategy .......................................................................................... 6 Review of the Literature ............................................................... 6 Arrangement of the Thesis .......................................................... 13 2. SUBSET -SUM NET ................................................................. 15 Resources ..................................................................................... 15 Subset-sum .................................................................................. 15 Problem Formulation .................................................................. 16 Simulation Results ...................................................................... 20 S umma.ry ...................................... .............................................. 25 3. K-CLUSTER NET .................................................................... 26 In-troduction ..................................... : ........................................... 26 K-Cluster Connection Weights ................................................... 28 K-Cluster Network Stability Analysis ........................................ 29 Results .......................................................................................... 31 4. TASK SCI-IEDUI.ER ................................................................................. 32 Introduction ................................................................................. 32

PAGE 6

vi S-trategy ........................................................................................ 34 Problem Description .................................................................... 35 Network Balancing ...................................................................... 36 Simulation Results (K=3) Network ............................................ 48 Simulation Results (K=5) Network ............................................ 50 Simulation Results (K=7) Network ............................................ 52 Results Discussed ........................................................................ 55 .An ExamPle Scheduler ................................................................ 55 5. CONCLUSION .......................................................................................... 59 APPENDIX A. Scheduler Code Listing ............................................................................ 61 REFERENCES .................................................................................................. 68

PAGE 7

CHAPrERl INTRODUCTION In today's dynamic society, there is a constant demand for tasks to be performed. These tasks must be performed promptly and productively. Although it would be desirable to have unlimited resources, all resources are finite. It is necessary to manage these resources efficiently. Effectively allocating resources to tasks is the function of a task scheduler. While. ensuring tasks are being completed promptly, it is important that the task scheduler is maximizing the use of all available resources If all available resources are being used at maximum capacity, the productivity will be high. In other words, if the sum of the resources being used at any given period of time is equal to the sum of the available resources, it is safe to infer that the tasks being performed productively. This resource allocation problem is the classic subset-sum problem where the subset-sum is equal to the resources available. Despite years of study, there are no polynomial-time algorithms to solve the subset sum problem [3]. The time to solve a subset-sum problem grows expc;mentially with the size of the problem. Often, a non-optimal

PAGE 8

solution is adequate for most applications, in which only requirement is that the solution is nearly optimal and can be achieved within a reasonable amount of time. 2 In 1982, Geoffrey Hinton and David E. Rumelhart in [11], writing with James L. McClelland came up with a name for a class of problems they were modeling. They called it Parallel Distributed Processing ( or PDP). They were using these models to solve complex problems in a near optimal manner. These models consisted of large number of simple and similar processors which were modeled after the neurons in the human brain. There were no supervisor processors and each processor was sharing the computation load equally. With the advent of Very Large Scale Integration (VLSI) circuits, PDP models were easily implementable and thus became very popular [15]. These models are also known as Artificial Neural Networks. James M. Macmillan, and Edward Hok-Lin Chang of University of Colorado have applied these models in [9] and [2] to solving the task scheduling problem. They have suggested further research. This thesis builds on their work and analyzes the performance of larger and more complex task scheduling problems.

PAGE 9

3 Puroose of the Study It is best to define the problem first. Task schedulers that are currently in the field are weak. Almost all of these task schedulers use priority numbers assigned to tasks to decide which task is next on line. They do not look at the resource constraints at the time of scheduling. An active task is executed until a resource it requires is. unavailable. At this time the task is put to sleep (or shelved) and the next task on line is made active. This type of scheduling results in lower productivity. A Task Scheduler: An Example Task scheduling problems are hard to solve. Task schedulers that consider availability of resources are known as Resource Constrained Schedulers. Job Shop Scheduling is. a class of resource constrained scheduling and have been studied in [1], [7], [10] and [4]. Chang in [2], talks about resource constrained schedulers and has suggested some excellent reference material on early research in this field. He also points out that until the arrival of neural networks, the optimization techniques used by the resource constrained schedulers required large computing power and were impractical. The reason being that Resource-Constrained Scheduling problems fall under a well known classical problem known as Non-deterministic Polynomial Time Complete (NP-

PAGE 10

Complete) Problem. To date, no one has found an algorithm to solve these problem in polynomial time. 4 An example task scheduling problem is explained here as a frame work for further discussion. In the telecommunication industry, voice messaging is becoming a common and popular feature. People call a messaging center to. record a message they want to be delivered. Then via the phone, they specify the time the message is to be delivered, the destination (phone number), and the priority of the message. The customer has an option of specifying a priority number from 1-10. For example, an urgent message could be identified as priority 1 as opposed to a non-critical message which could be identified as priority 10. The user then hangs up the phone. From there on, it is the responsibility of the task scheduler to deliver the message to its destination at the appropriate time. The message is split into multiple segments at the time of recording. To play a message segment the digitized voice message segment should be loaded into cache memory. Instead of loading one complete message into the cache memory and playing one message at a time, message segments belonging to different messages are loaded into the cache memory and played concurrently. Although different cashed message segments play concurrently, each segment belongs to a different message and thus will have a unique destination and will not interfere with the other

PAGE 11

segments being played. There are two banks of cache memory which work alternatively. While one is playing segments of messages, the other is being loaded with the next segments of messages. At the next period of time, the banks are switched and these segments are played. All segments of a message should be played at consecutive time periods. The following notations will be used for segments and size of segments: number of segments for message n = k, 5 Segment size of message n (Resource required I or Cost) = C, Size of Cache Memory (or Target Score) = R Kbits Total Cashe Memory used (or Score) = S Kbits At the time of recording, a message can be digitized at 64Kbit&'sec, 32Kbit&'sec, 16Kbit&'sec or 8Kbit&'sec. The quality of the voice being played back is best at 64Kbit&fsec and tolerable at SKbitS'/sec. At the time of recording the customer has a choice. While the customer is charged less for lower bandwidth the quality of the message recorded will be lower. All segments are one second long. This means a message recorded at 64KbitS'/sec will have a segment size of 64Kbits ( 8Kbytes). Similarly a message recorded at 8Kbit&fsec will have a segment size of 8Kbits (lKbytes).

PAGE 12

Scope of the Study In the last couple of years, artificial neural network task scheduling models have been studied. These studies have recommended further research. Here a task scheduler is built and used to solve a task scheduling problem. Strategy The strategy is to build on the results of Macmillan's and Chang's work in [9] and [2]. A step back is taken to study a few other models of the subset-sum network. The results are then compared and the best subset-sum model is chosen. Wolfe and others have studied the K-cluster network and have reported good results in [14]. This K-cluster network is combined with the subset-sum network to form a hybrid network to solve the task scheduling problem. This network is used on a Centralized Voice Messaging System to schedule the delivery of voice messages. Review of the Literature Vectors are bold lower case letters. b are vectors The ith element of vector b is hi. Example vectors: a & 6

PAGE 13

7 Matrices are bold upper case letters. Example W is a matrix. The element in ith row and jth column is Wij. Scalars are upper and lower unbolded letters. Kn is the number of time periods Task n requires for completion. rij is the resource job j requires at time period i. R is the total amount of resources available to the system. R stands for available resources. Si is the amount of resources used by the system at time period i. S is sometimes called the score. W is the weight matrix. Woo WOI ... WOn Wto ............... wtn : Wmo ............... w11111 Wij is the connection weight from node ito node j. Artificial Neural Networks Artificial neural networks, also known as Parallel Distributed Processing (PDP) models are modeled after our brain. Rumelhart and Hinton give a frame work for modeling these networks in [8]

PAGE 14

and [11]. The following are some aspects of the network they describe in detail in this paper: 1. A set of processing units. These units mimic the neurons. 2. A state of activation. Each unit is in a state of activation. The activation corresponds to the excitation of the neuron. a(t) Pattern of activations at time t. a(t) Activation of unit i at time t. 3. An output function for each unit. This function relates to the creation of the action potential generated by the neuron. These action potential travel along the axons. o;(t) = f(a(t)) 4. A pattern of connectivity among units. This pattern is the knowledge base for the network. These correspond to the axons. the paths along which the action potential travel. This conveniently represented by a weight matrix W. If Wij is non zero. a connection exists from unit ito unit j. 8

PAGE 15

5. A propagation rule. The propagation rule is what converts the potential arriving on the axon to an input. This function is performed by the synapses. net(t) = Wo(t) 6. An activation rule. The function of the activation rule is to change the state of activation of a neuron depending on the net input received from the synapses. a(t) = F(net;(t)) = F(Lw!ioi) j 7. A learning rule. This is the method by which the connection patterns are changed. This corresponds to the growing of new axons and dendrites. This is also known as the Hebbian rule and was first introduced by Hebb in [5]. A learning rule will not be used in this study. Our study concentrates on the connections and weights required to perform the task scheduling function. 9

PAGE 16

Organizations of the Neural Networks In a PDP model the activation units are organized into different levels. Figure 1. Network Organization Rumelhart and McClelland have organized the network into three types in [11]. They are: top-down bottom-up interactive 10 The top-down and bottom-up organizations can be grouped together as a non-interactive organizations. In the non-interactive organization an activation unit may not interact with a unit more than one layer away. The type of organization under consideration is the interactive organization, where any unit can interact with any other unit. Activations can flow in any direction and to any unit,

PAGE 17

11 with no layer restrictions. The initial activations of the units represents the input to the network. The connection weights represents the knowledge of the network. For the task scheduler these connection weights represent the type of scheduling. For example, the resources available (or target scoreR) and the number of time slots required to perform a task (K) are represented by the connection weight. Mter the network has settled, the initial activations represents the output of the network. Interactive Models The interactive model is the one which will be used for the task scheduler. Each unit represents the state of a task at a specific time period. When the network settles, the final activation of a unit represents whether a task has been selected for execution for that time period. Activated units represents selected tasks, while inactivated units represents tasks that have not been selected. Interactive Activation Model In the interactive activation model, we are interested in the units which could take on any value in the range [0, 1]. The units represent the state of a task at a specific time period. A 0 means

PAGE 18

12 the task has not been selected for that time period. A 1 means that the task has been selected for that time period. The information sent out by each unit is the product of its activation and the interconnection weight between the unit and the unit to which the information is being sent. The net input is the algebraic sum of the information received by each units. Let netj be the net input to unit j. q'(t + 1) 1) = q(t) + 1](1 neG); if neG> o = q(t) + TJ(neG) if netJ<= o The Energy Function Netj is a simple calculation which provides an indication to increase or decrease the current activation. It is a simple and local calculation. The assumption is that if positive connection weights are selected the connected units work together. If they are negative, the units are fighting each other and only one of the two units can be active at the final state of the network.

PAGE 19

13 With the above basic assumption (and Wij = Wj-D the activation update ensures that the energy of the network decreases as the activations are changed. The activation updates ensures that the energy of the network decreases locally. However it does not ensure that it can reach the lowest energy of the network. Local Minima As explained in the previous section, the activation updates do not ensure that the network will settle down at the lowest energy. The network may get stuck in a local minima [15] and never recover. Simulated Annealing A process called simulated annealing has been used to move the activations out of the local minima. This is a probabilistic method which works, but if overdone it can also move the activations away from the global minima. Simulated annealing is also discussed in [13]. Arrangement of the Thesis Chapter 1 introduced the task scheduling problem and defined the purpose of this study. It discussed a task scheduling

PAGE 20

problem in detail and outlined the strategy of this study. Finally, an overview of artificial neural network was given. 14 Chapter 2 compares different models of subset-sum network. The are then simulated and from the results of the simulation one model is chosen for solving the task scheduling problem. Chapter 3 discusses the work that has been done on the K cluster network and explains in detail how this network is modeled. Chapter 4 brings together the subset-sum and the K-cluster network models to solve the task scheduling problem. The results of the scheduler are discussed in depth. Chapter 5 uses the task scheduler on a few task scheduling problems. The results are discussed here.

PAGE 21

CHAPrER2 SUBSET-SUM NEURAL NET Resources Resources are the limiting factor for scheduling tasks. A task can be scheduled only if all the resources required by that task are available. If a task requires few resources1 it may be possible to schedule another task along with it. When multiple tasks are being scheduled for the same period of time, the constraint is that the sum of the resources being used by these tasks should be less than or equal to the amount of resources available for that time period. A task scheduler requires a component which assures that the total amount of resources required by the scheduled tasks are less than the resources available. This is the Subset-sum component of the task scheduler. Subset-sum The subset-sum problem poses an optimization problem. If C={ c1, c2, cg ........ en} is a set of positive numbers whose sum is T, find a subset of C whose sum is R. The subset-sum problem is a simplified 0-1 knapsack problem. In the 0-1 knapsack problem, a thief has a choice of selecting from a set of items X={xl, x2, xg ........ xn}, whose values are v2, vg ........ vnl and sizes are S={sl, s2, sg ........ snl. The only limitation the thief has is the size of a

PAGE 22

16 knapsack. If the size of the knapsack is R, which items of X={xl, x2, xg ........ xnl will the thief chose to maximize the value of the stolen goods. The knapsack problem becomes a subset-sum problem if the value V is directly proportional to the sizeS. Problem Formulation In our example task scheduling problem, the amount of cache memory required by a task can be considered to be C Kbytes ={cl, c2, cg ........ Cn}. The cache memory available to the Centralized Voice Messaging system is R Kbytes. Task n requires Cn Kbytes of cache memory. The task scheduler should select tasks, so that the sum of the cache memory required by the selected task is approximately equal to R Kbytes. For the subset-sum problem each task is mapped to a single processing element (or neuron). This processing element is referred to as a node. A task is selected if its node is on (or activated) when the network reaches a steady state. If it is off, the task is not selected. Four different models of subset-sum neural nets were considered. The first was the simplest and the fourth the most complex. Subset-sum 1 Each node is connected to every other node with a connection weight of the negated cost of the other node ( -Ck). This means that the net input to each node is the sum of the cost of the active nodes. If the external connection to each node is the target score (R), the node compares the target score with its net input and adjusts its activation accordingly. If the net

PAGE 23

17 input is less than the target score (R), the node tends to activate itself. If the net input is higher than the target score, the node tends to de-activate itself. Each node is adjusting its activation to satisfy the subset-sum constraint. This process is being done concurrently at each node. When the network runs to completion, it is expected that the sum of the cost of all active nodes equals the target score at each node. The following diagram shows this network: -Ck 0 0 0 R Figure 2. Subset-sum 1 Network Model Subset-sum 2 The connection weights of the first network were not symmetric. This network builds on the first network in order to make it symmetric. The connection weights were made symmetric by setting them to (Cj"'Ck). This change made it necessary to set the external input to RCj. (It can be easily seen that Cj can be factored out from the net input.)

PAGE 24

0 Figure 3. Subset-sum 2 Network Model Subset-sum .a The third network was from the work doneby Wolfe and others in [l'i The value for ALPHA was selected to be 0.5. This network is referred to as the BASE model for the Subset-sum problem. -(2.0 Cj *Ck) 0 0 ((2.0*R) ALPHA) c Figure 4. Subset-sum 3 Network Model

PAGE 25

19 Subset-sum While running some simulations of subset-sum 3 network, it was noted that this network could be improved by adding a constant value to the external input. Different values were tried for this constant. A value of 0.05 gave the best results. This network is identical to subset-sum 3 network except for the modification to the external input. 0 ( (( 2.0 R ) 0.5 ) C') + 0.05 Figure 5. Subset-sum 4 Network Model Subset-sum fi This network is from the work done by Wolfe and others in [17]. I came across this network at the latter stages of this study. Some simulations were run to compare the results with the previous 4 types of the network.

PAGE 26

20 0 ( score*Ci)(0.5*Ci*Ci) Figure 6. Subset-sum 5 Network Model Simulation Results Many 15 node simulation runs were made on each type of the above Subset-sum network. The target score (R) was always 1. The task costs for each run were. randomly initialized and then normalized to 1. The initial activation for each node was randomly initialized to a very small number. For each run, the percentage error of the score was calculated. The runs were grouped into ranges of percentage errors. The ranges were increments of five. The following charts summarize the results by showing the proportion of percentage errors for each network.

PAGE 27

80 80 70 80 &0 2 .... 0 40 30 20 10 0 [0-5] [5-10] % error VS % runs Subset-sum 1 network 21 [10-15] [1&-20] [20-25] [25-30] [30-36] [35-40] [40-45] % error ranges Figure 7. Subset-sum 1 Network Results

PAGE 28

IO-&J [6-10) %error VS % runs Subset-sum 2 network 22 [10-16] 116-20] [20-26] [26-30] {30-36) [3&-40) [40-46] % error range Figure 8. Subset-sum 2 Network Results

PAGE 29

23 % error VS % runs Subset_sum 3 network 90 80 70 60 Ill c 60 ::J ... :/=40 30 20 10 0 [0-6] [6-10] [10-16] [16-20] [20-26) % error range Figure 9. Subset-sum 3 Network Results

PAGE 30

24 % error VS % runs Subset-sum 4 network 80 80 70 60 Ill &0 c 2 40 30 20 10 0 [0-&) [5-10] [10-15] [15-20] [25-30) %error range Figure 10. Subset-sum 4 Network Results

PAGE 31

25 % error VS % runs Subset-sum 5 network 90 80 70 60 Ill 50 c :J ... ':f:..co 30 20 10 0 [0-5) [&-10] [10-1&) [1&-20] [20-30) %error range Figure 11. Subset-sum 5 Network Results Summary The results of the simulations suggest that the subset-sum 4 network performed better than the first three. This network was chosen to build the task scheduler network. The subset-sum 5 network also performed well. Prior to this study this network was analyzed by Wolfe and others in [17] yielding the same type of results.

PAGE 32

CHAPrER3 K-CLUSTER NEURAL NET Introduction The K-cluster network has been studied in detail by Wolfe and others in [17], and have reported good results with this network. This K-cluster network (without any modifications) is used to build the task scheduler analyzed in this thesis .. Most of the information presented here are from the class notes [16] and the publication [17]. K-cluster networks selects K winners with an additional criteria that the selected winners are clustered together. The network can be viewed as selecting an corner with K number of 1's and that the 1's are clustered together (wrap around clustering is allowed). (The N-cube or Brain State in a Box model was developed byJ.A. Anderson (1977) [11]). The following is a 3-cube model depicting a 2-cluster 3 node network.

PAGE 33

(0,1,11 (1,1,11 (0,0,11 I / / / / / / I / (0,0,01 / / / / / / / / I I (0,1,01 }----------+------(1,1,01 27 The K-cluster network settles on one of the 3 2-cluster corners (marked by a dots). Unfortunately with wrap around clustering, the 3-cube 2-cluster corners are the same as the 2-winner corners. Since it is impossible to draw a 4-cube in a 2 dimensional space, a graphical representation of a 4 cube is not attempted here. Although all K-cluster corners are considered feasible solutions, not all of these comers are optimal solution. In [17] the definition of the optimal solution of the K-cluster state corresponds to the largest area under the graph of the initial activation1s. This is shown in the followllig diagram. 1.0 Kcluater Initial a.:tivation 5-cl..-ter 13 node network

PAGE 34

28 K-Cluster Connection Weights In [17], the K-cluster network is defined as a Hopfield-style [6] network with an additional property that each unit sees the same distribution of connection weight. This implies that if one row of the connection weight matrix W is known, all other rows of W can be easily obtained by shifting the known row circularly. In [16] and[17], it is shown that this property reduces the net input to a simple discrete circular convolution of row 1 of the weight matrix W with activation vector a. Wif = if 8(i,j) (k-1)/2. othe1Wise where 8(i, j) is the minimum distance between the indices i and j

PAGE 35

w 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 = -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 neti = *aj +a Since the rows of the connection matrix Ware shifted versions of row I, the net input can be found_by convolving row 1 ofW with the activations. This is explained clearly in [ 17]. K -Cluster Network Stability Analysis 29 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 The stability analysis allows us to determine a value for the external inputs, so that k states are stable for a given K. With interactive activation updates, it can be easily seen that a corner state is stable if the net input to

PAGE 36

the active units are positive and the net inputs to the inactive units are negative. ( ( ) [1-Cli(t)] 8i t + 1) = 8i t + neti(t) [ai(t) ] The comer states are stable if, 1 a(t) = 1 and net(t) 0 and 2. 8i(t) = 0 and net(t) < 0 ifneti(t) :::; 0 ifneti(t) > 0 The net input to the inactive unit at the edge of the cluster is : neti = ( k-((k-1)/2))*(-1) + e < 0 1. e. e < ( k + 1) /2 Similarly the net input to the active unit at the edge of the cluster is: neti = ( k -1 ((k-1)/2))*(-1) + e 0 1.e. e (k-1)/2 30 From the above two conditions, a K-cluster network will be stable only if the external input e satisfies the following condition:

PAGE 37

31 (k-1}/2 :s; e < (k+l}/2 Results Several k-cluster networks were simulated yielding positive results. In [17], the network has been observed to be stable and 100% of the solutions were observed to be feasible solutions. 50% of solutions were found to be optimal. It is also noted in [17] that many of the non-optimal solutions were close to the optimal solutions.

PAGE 38

CHAPrER4 TASK SCHEDULER Introduction This chapter analyzes the task scheduling problems investigated by Macmillan in [9] and Chang in [2] in more detail. Macmillan combined the subset-sum network and the K-cluster network to build a non-preemptive task scheduling network. Similar to Macmillan's network, to build a preemptive task scheduler a K-winner network could be used instead of the K-cluster network. This study concentrates on the non-preemptive task scheduling problem only. T ODD ODD DOD ODD ODD ODD ODD Time Slolll DDDDODDDD DDDDDDDDD DDDDDDDDD DDDDDDDDD DDDDDDDDD DDDDOvDDD DDDDDDDDD KCIUBter Networ Sublet....,.. network nodee lnitialiled to preference values. Figure 12. Task Scheduler Network Layout

PAGE 39

33 The layout of the task scheduler network is shown in Fig. 1. The subset-sum and K-cluster networks, discussed in Chapters 2 and 3, are sub networks of the task scheduler network. The subset-sum sub-network runs vertically (column oriented) and the K-cluster sub-network runs horizontally (row oriented). The connection weights are not shown for clarity of the diagram. Each row represents a task and each column represents a time slot (or time period). The cost of each task is represented in the connection weight of the subset-sum sub-network. Similarly, the time period required to complete a task is represented by K in the K-cluster networlt. Each row (i.e. each task ) could have a different value forK but in our study here K will be the same for each row. In our Voice Messaging example, K identifies the length of the message in seconds. The cost of each task represents the bandwidth at which that message was recorded. Higher bandwidth costs more ( cache memory) and lower bandwidth will cost less ( cache memory). The resources available at each of the time slots are represented by the external inputs to the nodes. This is the cost the task scheduler schedules around. If the tasks are scheduled such that the total cost of each time slot is equal to the cost of available resources, the tasks execute efficiently. If the cost of the scheduled tasks exceeds the available resource the schedule becomes an invalid schedule. It is important to note here, that our scheduler provides us an approximate solution and that the total cost need not be exactly equal to the cost of available resource but within the proximity of it.

PAGE 40

34 Lastly, the preference of a time slot for each task is represented by the initial activation (or the Preference Value) of the node. If the node, represented by row a and column b is initialized to a high value, the preference for task a to be performed at time slot b is also high. Strategy The task scheduling network is built by integrating the subset-sum network discussed in Chapter 2 with the K-cluster network discussed in Chapter 3. Each of these networks are referred to as sub-networks. The integration of the two sub-networks produces undesirable effects on the performance of each individual sub-network. It seems that the performance of one sub-network negatively affects the strength of the other sub-network. In order to reduce this negative effect on the performance of the scheduler, the strengths of the two sub-networks should be balanced. The balancing of the two sub-networks are achieved by introducing a Balancing Constant to the subset-sum sub-network. The Balancing Constant scales the connection weights of the subset-sum network. The performance of the scheduler network is analyzed by changing the Balancing Constant. The performances of the network are compared and the best Balancing Constant is selected. Finally, simulations are run with balanced and unbalanced scheduler networks and the results discussed.

PAGE 41

Problem Description The task scheduling problem described earlier may be defined as follows: Given a finite set S = [ Sl sz ... Sn] consisting of n elements Vll Vl'J. VIm and v = V21 Vnl Vn2 Vnm n where LSI = N i = 1 and a target t < N find a n*m matrix A = a11 a12 a1m azl ................. Gil Gtm where C1J = 1 or 0 (the 1s are clusterd together) n such that L s; ai == t (for each j) i = 1 m and L av = K for each j j = 1 m and L Vif "'ai is maximized for each i j = 1 35

PAGE 42

36 The m n matrix A is the result produced by the task scheduler. Each row of matrix A represents a task being scheduled. There are 'n' rows representing 'n' tasks. A time slot or a time period is represented by a single column in A. If aij is one, task i has been selected for execution at time slot j. If it is zero, task i has not been selected for execution at time slot j. Consider the vector S, to be the cost vector for the tasks. The cost of executing task i during a time slot period is Si. The condition n :Ls;*a;i t i = 1 maximizes the cost at each time slot. The cost of executing the selected task is approximately t. m The condition :Lai = k ensures that each task is scheduled for j = 1 only K time slots. The condition that ls in aij are clustered in each row ensures that the tasks are scheduled non-preemptive. Finally, the matrix V is the preference value for executing a task. If Vij is high, the task i has high preference to be executed at time slot j and vice m versa. The condition to maximize :Lvv*ai ensures that the preference j = 1 values for each task is maximized. Network Balancing After many simulations of the scheduler network, it was concluded that the performance of the network was not acceptable. The row oriented K cluster sub-network and the column oriented subset-sum sub-network were

PAGE 43

37 negatively affecting each other. When the K cluster sub-network was stronger than the subset-sum sub-network, the resultant scores for each time slot were off by a large amount. It seemed that the effects of the subset-sum network were being ignored. When the subset-sum sub-network was stronger, the resultant network performed poorly in picking a K cluster. The selected time slots were either not clustered together or they did not sum up to the expected value of K. The following are some examples of an unbalanced network.

PAGE 44

T a s k s Neural Network: 1 D Jobs 10 llme slots K 3 Task Costs: 0.04 0 05 0 05 0.06 0.07 0.10 0 15 0.20 O.ZJ 0 33 Sc.ores : 0.1 0.1 0.1 O.l 0.3 0.2 0.2 0.2 0.3 O.l An Unllalananl Task scheduler 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 l1me Slots ---- w CXl

PAGE 45

T a s k s Neural Network: 1 0 Jobs 15 Tone Slots K 7 Task Costs: 0.04 0.05 0.05 0.06 0.07 0.10 0.15 O.ZO O.Z3 0.33 Scores : 0.9 0.9 0.9 0.9 0.9 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.9 0.9 An Unbalanced Task scheduler D D D D D D D D D D D D D D D D D D D D D D D D D D D D DDDDD" D D D D D D D D D DDDDD" D D D D D D D D D D D D D D D D D D D D D D D D 1lme Slots----> VJ \0

PAGE 46

T a s k s Neural Networtc: 10 Jobs 40 Tbne Slots K o 9 Task Ulsts: 0.04 o.os o.os 0.06 0.07 0 10 0.15 o.zo 0.23 0.33 Scoi"IIS : 0.5 0 5 0 5 0.5 0.5 0.5 0.0 0.0 0 0 0 3 0.3 0.3 0.3 0.3 0.0 0.0 0.0 0 4 0.4 0.4 0.4 0 4 0 4 0.4 0.4 OA 0 0 0 0 0 0 0.3 0.3 0.3 0.3 0.3 0.0 0.0 0.0 0.5 0.5 0.5 An Unbalanced Task scheduler oooooo 0 0 0 oooooo 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000000' 0 0 0 oooooo 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 lime Slots ____ """" 0

PAGE 47

41 In order to balance the network, a Balancing Constant was added to the subset-sum sub-network. There were two ways of using this balancing constant. Both these methods were tried out, however the second method performed better. The second method was utilized for the simulations results shown in this study. The first method was to scale the net input to a node at each iteration of the network. The net input to a node was differentiated as one contributed by the sub-set sum part of the network and the other contributed by the Kcluster part of the network. The balancing constant was used as a scaling factor to the net input from the sub-set sum network. netinput.scheduler = ( BC netinputsulnet_ sum ) + net-inputKdu.ster This method distorted the performance of the subset-sum sub-network considerably. The second method was to scale the normalized task costs and the target score at the initialization of the network. This enabled the network to run without differentiating the net inputs from the two different types of sub networks. Secondly, this method did not distort the affects of the subset-sum network as much as in method 1. The results of the scheduler network was plotted for different values of the Balancing Constant ranging from 0.1 to 0.5 The network was initialized with preference values and run with random costs for the tasks. The score (scheduled cost) for each time was calculated. The highest score was determined and averaged over 25 runs. This averaged highest score is labeled as the Maximum Average Score.

PAGE 48

42 In the following charts, the network Maximum Average Score is plotted as the independent variable and the Balancing Constant dependent variable. Average Max Error in Score VS Balancing Constant 300 2&o....--.-a. 200 %Error 150 100 .. __ .__. 0.1 0.2 0.3 0.4 O.li 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant 300 250 200 %Error 150 100 50 Average Max Error in Score VS Balancing Constant __ .__. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.8 1 1.1 1.2 1.3 1.4 1.6 Balancing Constant

PAGE 49

10 network K .=a 300 250 200 %Error 150 100 Average Max Error in Score VS Balancing Constant 50 0.1 0.2 0.3 0.4 0.& 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 10 network K .=a 300 250 200 %Error 160 100 Balancing Constant Average Max Error In Score VS Balancing Constant 60 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.6 Balancing Constant 43

PAGE 50

10 network K =5 Average Max Error In Score VS Balancing Conant 300 200 %Error 150' 100 0.1 0.2 0.3 0.4 0.6 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Conant Average Max Error In Score VS Balancing Conant 300 ..... .... 200 %Error 150 100 60 __ 0.1 0.2 0.3 0.4 0.6 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.6 Balancing Conant 44

PAGE 51

300 250 200 Average Max Error in Score VS Balancing Constant %Error 150 300 100 50 0.1 0.2 0.3 0.4 0.& 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant Average Max Error in Score VS Balancing Constant 2sor-.--.6....._ 200 %Error 150 100 &0 0.1 0.2 0.3 0.4 0.& 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant 45

PAGE 52

10 network K .= 1 300 250 200 %Error 150 100 Average Max Error In Score VS Balancing Constant 60 0.1 0.2 0.3 0.4 0.6 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.6 Balancing Constant 10 network K .= 1 Average Max Error in Score VS Balancing Constant 300 .... ... 200 %Error 160 100 60 0.1 0.2 0.3 0.4 0.6 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant 46

PAGE 53

10*30 network K.:: 1 Average Max Error In Score VS Balancing Constant 300 2sor-.-.... -....... 200 %Error 150 100 &0 .. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant 10*40 network K.:: 1 Average Max Error In Score VS Balancing Constant 300 250y-___ .. 200 'lo Error 160 100 60 __ 0.1 0.2 0.3 0.4 0.& 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Balancing Constant 47

PAGE 54

Simulation Results CK=3) Network A 10*10 Unbalanced Network.: BQ .= 1.0 Max Score Error 1 0.8 y 0.6 0.4 0.2 10 Network K=3 Unbalanced --Ideal Satisfaction ---Scheduled satisfaction 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 & & & 6 6 6 7 7 7 7 8 8 8 9 9 9 1 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 5 8 1 4 7 0 runs A 10*10 Balanced Network.: BC;: 1.3 Max Score Error 1 0.8 y 0.6 0.4 0.2 10 Network K=3 Balanced (BC.3) 0 Ideal Satisfaction ---Scheduled satisfaction 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 & 5 & 6 6 6 7 7 7 7 8 8 8 9 9 9 1 0 3 6 9 2 5 8 1 4 7 0 3 6 9 2 I 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 runs 0 48

PAGE 55

10 Unbalanced Network.: Jill.:: l..Q In this case the results seems to be good, but the scheduler failed to cluster the time slots. 1.2 1 Max Score Error 0.8 y 0.6 OA 0.2 10*20 Network K=3 Unbalanced ---Ideal Satisfaction --Scheduled satisfaction 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 6 6 6 6 7 7 7 7 8 8 8 8 8 8 1 0 3 6 9 2 6 8 1 4 7 0 3 9 2 6 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 runs 0 10*20 Balanced Network.: BC.:: 0.75 49 In order to improve the performance of the K cluster network the subset-sum network was weakened. This was done by selecting a balancing constant less than 1.0. Here a balancing constant of 0.8 is chosen. At the cost of a 15o/o score error the performance of the network was improved.

PAGE 56

1.2 1 Max Score Error 10*10 Network K=3 Balanced (BC=0.8) -- Ideal Satisfaction ---Scheduled 0.8 ,.....,.....N\ y 0.6 0.4 0.2 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 6 6 6 6 7 7 7 7 8 8 8 8 9 9 1 0 3 6 9 2 6 8 1 4 7 0 3 6 9 2 6 8 1 4 7 0 3 6 9 2 6 8 1 4 7 0 runs 0 Simulation Results CK=5) Network 10 Unbalanced Network: 00.:: 1...Q 10 Network K=6 Unbalanced ---Ideal Satisfaction --Scheduled satisfaction 0.8 0.2 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 I 6 6 6 7 7 7 7 B 8 B 9 8 8 1 0 3 6 9 2 6 8 1 4 7 0 3 6 8 2 6 8 1 4 7 0 3 6 9 2 6 8 1 4 7 0 runs 0 50

PAGE 57

10*10 Balanced Network BC .= 1.4 Max Score Error 10*10 Network K=3 Balanced K=1.4 ----Ideal Satisfaction ---Scheduled satisfaction 0.8 y 0.6 0.4 0.2 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 6 6 6 6 7 7 7 7 8 8 8 9 9 9 1 0 3 6 8 2 6 8 1 4 7 0 3 6 8 2 6 8 1 4 7 0 3 6 8 2 6 8 1 4 7 0 runs 10*10 Balanced BC.:: 1.5 Max Score Error 10*10 Network K"'3 Unbalanced 0 - Ideal Satisfaction ---Scheduled satisfaction 0.8 0.2 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4-4 4 6 6 6 6 6 6 7 7 7 7 8 8 8 9 9 9 1 runs 0 51

PAGE 58

Simulation Results CK=7) Network 10 Unbalanced Network: B.Q .= .l.Q 2 1.6 y 1 0.5 10*10 Network K Unbalanced Ideal Satisfadlon --Scheduled satisfaction -Max Score Error 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 5 5 6 8 8 8 7 7 7 7 8 8 8 8 8 8 1 0 3 8 8 2 5 8 1 4 7 0 3 8 8 2 6 8 1 4 7 0 3 8 8 2 6 8 1 4 7 0 runs 0 10 Balanced Network :00.= 1.5 2 1.6 y 1 0 5 10*10 Network K=3 Balanced BC.5 Ideal SaUsfadlon -Scheduled satisfaction -Max Score Error 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 6 8 8 8 7 7 7 7 8 8 8 9 9 8 1 0 3 8 8 2 6 8 1 4 7 0 3 8 8 2 6 8 1 4 7 0 3 8 8 2 6 8 1 4 7 0 runs 0 52

PAGE 59

10"'20 Unbalanced Network: BC:: 1.0 2 1.6 y 1 0.5 10*20 Network K=7 Unbalanced Ideal Satisfaction ---Max Score Error ---Max Score Error 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 & & & 6 6 6 7 7 7 7 8 8 8 9 9 9 1 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 runs 0 10"'20 Balanced Network: BC:: 1.3 2 1.& y 1 10*20 Network K=7 Balanced BC=1.3 Ideal Satisfaction ---Scheduled satisfaction ---Max Score Error Max Score Error 0.& 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 & 6 6 6 6 7 7 7 7 8 8 8 9 9 9 1 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 & 8. 4 7 0 3 6 9 2 58 1 7 0 runs 0 53

PAGE 60

10 Unbalanced Network.: BC.:: .LQ 2.& 2 -'""'.A '"'""'AI',.,'-"'\ y 1.& 1 0.5 10*30 Network K=7 Unbalanced --Ideal Satisfaction ---Scheduled satisfaction ---Max Score Error 1 4 7 1 1 1 1 2 2 2 3 3 3 4 4 4 4 & & & 6 6 6 7 7 7 7 8 8 8 9 9 9 1 o 3 6 9 2 & a 1 4 1 o 3 6 9 2 6 a 1 4 1 o 3 6 9 2 6 a 1 4 1 o runs 0 10 Unbalanced Network.: BC.:: 1.0 2.& 10*40 Network K=7 Unbalanced ---Ideal Satisfaction ---Scheduled satisfaction ---Max Score Error y 0.6 1 4 1 1 1 1 1 2 2 2 3 3 3 4 4 4 4 6 6 6 6 6 6 1 1 1 1 a a a 9 9 9 1 o 3 6 9 2 6 a 1 4 1 o 3 6 9 2 6 a 1 4 1 o 3 6 9 2 6 a 1 4 1 o runs 0 54

PAGE 61

55 Results Discussed The Average Maximum Error in Score vs. Balancing Constant charts show that as the subset-sum sub-network increases in strength the score errors decrease. This does not mean that a high Balancing Constant improves the performance of the scheduler. The performance of the scheduler depends also on the strength of the K-cluster sub-network. When the K-cluster sub-network is weak, the K-clustering property of the network is lost. Some-times the scheduled time slots were not scheduled and other times the number of scheduled time slots were not equal to K. These results imply that there must be a trade off between the accuracy of the target score and the clustering property. In the simulations here, the trade off was approximately 15o/o of the target score in order to keep the K clustering property. The scheduler performed better when they were balanced. An unbalanced scheduler performed poorly. An Example Scheduler In this section, the balanced task scheduler network was used as a scheduler for the Voice Messaging system explained in the Chapters 1 and The cost vectors were set to be proportional to the bandwidth of the voice recording. The Bandwidth costs of 64Kb/sec, 32Kb/sec and 8Kb/sec were set

PAGE 62

56 to 1.0, 0.5 and 0.25 respectively. Unfortunately, the normalizing of the cost vectors distorted the cost ratios a little. The 10*40 scheduler was initialized to schedule for 10 voice lines for a time period of: 40 seconds. The network parameters were initialized the following way: The bandwidths for the voice segments were randomly generated. The length of the voice segment indicated by the value of K in the K-cluster network was set to 5. The time at which a voice segment was to be played was indicated by g.iving a preference value for that time slot. This time period was generated randomly. Twenty continuous time slots, beginning at a randomly generated time, were set as preferred for each of the 10 voice lines. This implied a delay of 20 seconds for a voice response was acceptable. The preference values were initialized to 0.01. The maximum cost allowed per time slot was set to 1.0 This is referred to as the score. The best schedule for the above example produces a scheduler reward of 0.5 ( = 5 0.01 10) while the cost of the schedule for each of the 40 time slots should not exceed the score (1.0). The ideal reward, the scheduler reward and the maximum cost error indicate the performance of scheduler. For an optimal solution, the scheduler reward should be 0.5 and the maximum cost error should be 0.

PAGE 63

57 The following graph is the results of the scheduler. It shows that the scheduler performed near optimal preference of 0.5. There were some optimal solutions. The spikes on the graph indicates that for some runs the cost error exceeded the available cost. The maximum cost error was approximately 17%. 10*40 Network K=& An Example --Ideal Satisfaction --Scheduled satisfaction --Max Score Error Y 1.5 Max Score Error !1. : ... .c. .. J ... n ... A.:::::;. .. : ............ : ..... : ...... :.A ... .. 1 3 6 8 1 1 1 2 2 2 3 3 3 3 4 4 4 & & & 6 8 6 6 7 7 7 8 8 8. 8 9 9 9 2 & 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 3 6 9 2 & 8 1 4 7 0 3 6 9 runs The following charts show the results of the scheduler. The rows represent the 10 tasks (or voice lines). The columns are the 40 time slots the scheduler uses for scheduling. Each column represents 1 second of voice segment. A square box indicates a preference value assigned for that time slot. Each tasks was initialized to have 20 contiguous preferred time slots. The number of segments played was represented by K in the K-cluster sub network. These segments are required to be contiguous. The value of K was set to 5 for each task. The black dots in the diagram represent the final result of the scheduler. These are the time slots the scheduler picked for the

PAGE 64

58 tasks. The result should be such that the black dots are contiguous and they are all inside the square boxes. Muhum ,._.bllt Anrud c.e "'"Iii 0.47 eo. P11a.n Error 1J DlillillillillilDDD o o o o o o o o o o ODOOOOOOODDOiillil DO DO Figure 13. Scheduler Example 1. Muftun O.ti ..,.._d 0.5 C... ._.c.11nar 0 .DDDODDODDD!illillillillilDDODD ooooo DODO DO DDOD!illillillillilDDDDDDDD DDDDDDOD!illillillillilODOODDD ODDDDOD 00000 DDDDDDD!illillillillilOOOOOODD DDDDDDDD!illillillillilDDDOODO Figure 14. Scheduler Example 2.

PAGE 65

CHAPrER5 CONCLUSION Although the task scheduler network did not produce optimal outcomes, the solutions for the most part were feasible and within the proximity of the optimal solutions. On some occasions the solutions were not feasible solutions. For example, when the subset-sum sub-network was stronger than the K-cluster network, it was observed, that the clustering property of the network was being ignored by the network. This was because the stronger subset-sum sub-network was working harder to satisfy its constraints and thereby overpowering the k-cluster sub-network. The important observation from this study is that it is necessary that the two sub-networks are balanced. The balancing is very difficult to accomplish, especially when the network initialization parameters are different for each schedule. In this study the preference values (or the initial activations) of the tasks were stable while the costs were being changed for each schedule. The maximum average error for each schedule was plotted for various values of a network balancing constant. The balancing constant at which the maximum average error became zero was the point at which subset-sum sub-network over powered the k-cluster sub-network. The balancing constant that produced a maximum average error of 15% produced feasible solutions which were close to the optimal solutions.

PAGE 66

60 The performance of the scheduler network moves towards optimal performance when a high number of tasks are being scheduled. The reason being, the subset-sum sub network has a bigger pool of tasks to select from and thereby work with the nodes selected by the k-cluster sub-network instead of working against it. This allows the two sub-networks to work together. AB general purpose schedulers the PDP models of task schedulers do not perform well. But for specialized types of task scheduling, where the initial parameters are within a known range and the solutions are not constrained to be optimal, the PDP model performs adequately.

PAGE 67

APPENDIX A. Scheduler Code Listing ;; /* The scheduler : Row are K Cluster sub-networks Column are subset-sum sub-networks Code used for simulating the scheduler for the Voice' messaging problem. ; #include . #include #include #include ; Define Constants used. *I #define ITERATIONS 750 #define JOBS 10 #define Tll\1ESLOTS slots*/ #define :MAXA 1.0 #define MINA 0.0 /* this is the maximum number of jobs */ 40 ; this is the maximum number of Time #define SUBSET_CONST 2.0 /* should be 2 .0 normally */ #define BC 0.95 ; Balancing constant for the sub-networks ; /* Global variables used. *I extern Display theDisplay; int KLUSTER[JOBS]; int klust = 5; float STEP _SIZE= 0.1; float SAVE_SIZE; int ravi_count =0; int scheduler( the Window) Window the Window; { float initial_a[TIMESLOTS] [JOBS];

PAGE 68

float ia_save[TIMESLOTS] [JOBS]; float a[TIMESLOTS][JOBS]; float a_save[TIMESLOTS][JOBS]; float net[TIMESLOTS] [JOBS]; float normal_length, score, sum; inti, j, k,l, m, n, gx, gy, draw_size[2], nodes, time, offset; char string[256], tstr[32], scheduled_str[256]; FILE *fpl; int column; int distance; float rscore[TIMESLOTS], s[TIMESLOTS]; float ALPHA ; float penalty _factor[TIMESLOTS] [JOBS]; float ascore[TIMESLOTS]; float max_cost_error, total_score, max_reward, reward; float column_cost, column_cost_error; nodes =.JOBS; time = TIMESLOTS; score= 1.0; ALPHA = 0.5; ; Open a file for outout ; /* num of tasks to be scheduled ; /* num of time slots used by scheduler */ /* A constant used by the subset part ; if( (fpl = fopen("example.doc", "a")) == ){ printf("\nError Opening file \n"); return(O); } ; Init time slots required for each tasks *I for (i = 0; i < nodes ; i ++ ) { KLUSTER[i] = klust; } ; Initialize Activations : Connection weights for SUBSET problem. Randomly at 0.25, 0.50, 0. 75 Or 1.0 62

PAGE 69

j for(i=O, normal_length = 0; i< nodes; i++) { initial_a[O] [i] = ((float) (randQ%4 + 1)) 0.25 ; normal_length += (initial_a[O][i] initial_a[O][i]); } j Normalize the connection weights (ie. the costs) j normal_length = (float)sqrt(( double)normal_length); for(i=O; i< nodes; i++) { initial_a[O] [i] /= normal_length; } r Balance the subset network by BC j for(i=O; i< nodes; i++) { initial_a[O][i] = BC; ia_save[O][i] = initial_a[O][i]; } score= BC; j Initialize the preference values j forO = 0; j
PAGE 70

} r a[G+3)%time][i] = 0.01; a[G+4)%time][i] = 0.01; a[G+5)%time][i] = 0.01; a[G+6)%time][i] = 0.01; a[G+7)%time][i] = 0.01; a[G+8)%time][i] = 0.01; a[G+9)%time][i] = 0.01; a[G+10)%time][i] = 0.01; a[G+11)%time][i] = 0.01; a[G+12)%time][i] = 0.01; a[G+ 13)%time][i] = 0.01; a[G+14)%time][i] = 0.01; a[G+ 15)%time][i] = 0.01; a[G+16)%time][i] = 0.01; a[G+17)%time][i] = 0.01; a[G+ 18)%time][i] = 0.01; a[G+19)%time][i] = 0.01; max_reward += 0.05; a_save[j][i] = 0.01; a_save[(j+ 1)%time][i] = 0.01; a_save[(j+2)%time][i] = 0.01; a_save[(j+3)%time][i] = 0.01; a_save[(j+4)%time][i] = 0.01; a_save[G+5)o/otime][i] = 0.01; a_save[(j+6)%time][i] = 0.01; a_save[(j+7)%time][i] = 0.01; a_save[(j+8)%time][i] = 0.01; a_save[(j+9)%time][i] = 0.01; a_save[(j+10)%time][i] = 0.01; a_save[(j+11)%time][i] = 0.01; a_save[(j+12)%time][i] = 0.01; a_save[(j+ 13)%time][i] = 0.01; a_saye[(j+14)%time][i] = 0.01; a_save[(j+15)%time][i] = 0.01; a_save[(j+ 16)%time][i] = 0.01; a_save[(j+ 17}%time][i] = 0.01; a_save[(j+18)%time][i] = 0.01; a_save[(j+19)%time][i] = 0.01; Update the costs for the rest of the columns 64

PAGE 71

; for (i = 0; i (KLUSTER[l1'2) ) { net[m] [l] -= ( ( a[k] [l] ) ); } net[m][l] += ((((float)KLUSTER[l]}'2.0)); } } ; Calculate the net input for the subset part ; for(l = 0; I< time; I++) { for G = 0; j
PAGE 72

for (k = 0; k < nodes; k++) { ifG!=k) { net[l][j] -= (( a[l][k] (((SUBSET_CONST initial_a[l][k]) (initial_a[l][j] )) ))); } } net[l][j] += (((2.0score) -ALPHA) (initial_a[l][j])); net[l] [j] += 0.05; } } ; activations ., for (m = 0; m = 0)? (a[m][j] + (STEP_SIZE ( net[m][j]( MAXA-a[m][j])))) : ( a(m][j] + (STEP _SIZE(net[m][j](a[m][j] -MINA)))); net[m][j] = 0.0; r clear net for next iteration use., } } } ; Calculate reward for schedule ; reward = 0.0; for (i = 0; i 0.6) { reward+= a_save[j][i]; if(a[G+l)o/otime][i] > 0.6)reward += a_save[j][i]; if(a[G+2)%time][i] > 0.6)reward += a_save[j][i]; if(a[G+3)o/otime][i] > 0.6)reward += a_save[j][i]; if(a[G+4)o/otime][i] > 0.6)reward += a_save[j][i]; break; } 66

PAGE 73

} } j Calculate Max error j max_cost_error = 0.0; for G = 0; j 0.6)column_cost += ia_save[j][i]; } if ( column_cost > score) { column_cost_error = column_cost -score; if( column_cost_error > max_cost_error = column_ cost_ error; } } printf("\n%d: MaX Rewards = %1.5f Scheduler Reward = %1.5f Cost err = %1.5'' ++ravi_count,max_reward, reward, (max_cost_error/score)loO.O); fprintf(fp 1," \n%1.5f\to/ol.5f\to/ol.5f'', max_reward, reward, (max_cost_error/score)loO.O fclose(fpl); } 67

PAGE 74

REFERENCES [1] J. Barker and G. B. McMahon, "Scheduling for General Job Shop," Management Science. May 1985. [2] Edward Hok-Lin Chang, "Neural Network Approach to Resource Constrained Scheduling/' Master's thesis, University of Colorado at Denver, 1992. [3] Thomas; H. Cormen, Charles E. Leiserson and Ronald L. Rivest, Introduction to Algorithms, The MIT Press, 1990. [4] W. S. Gere, "Heuristic in Job-Scheduling," Management Science. Nov. 1966. [5] D. 0. Hebb, Edited byJ. A. Anderson and E. Rosenfeld, "The Organization of behavior," Neurocomputing: Foun.dation and Research, 1943. [6] J. J. Hopfield, "Neural Networks and Physical Systems with Emergent Collective Computational Abilities," Proceedings of the National Academy of Science, 1982. [7] J. B. Lassere, "An Integrated Model for Job-Shop Planning and Management Science. 1992. [8] Richard P. Lippmann, "An Introduction to Computing with Neural ' Nets," IEEE ASSP Magazine, April, 1987.

PAGE 75

[9] James M. Macmillan, "Solving the Task Scheduling Problem using Neural Networks," Master's thesis, University of Colorado-Denver, 1989. [10] J. Carlier and E. Pinson, "An Algorithm for solving the Job-Shop Problem," Management Science. Feb. 1989. 69 [11] D.E. Rumelhart and G.E. Hinton, "A General Framework for Parallel Distributed Processing," Parallel Distributed Processing: Exploration in the Micro Sructure of Cognition, Volume 1, The MIT Press, 1989. [12] J. A. Shaw, "Solving Optimization Problems using the Recurrent Neural Networks," Master's thesis, University of Colorado at Denver 1991. [13] H. Szu, "Fast Simulated Annealing," AlP Conference on Neural Networks for Computing, 1986. [14] W. J. Wolfe, et al. "K Winner Networks," IEEE Transactions on Neural Networks, Jan. 1991. [15] W. J. Wolfe, "Introduction to Neural Networks," Class Notes Part I, University of Colorado at Denver. Summer 1991 [16] W. J. Wolfe, "Introduction to Neural Networks," Class Notes Part II, University of Colorado at Denver, 1991. [17] W. J. Wolfe:, et al. "Homogeneous Networks," Manuscript, University of Colorado at Denver, May 1992. [18] W. J. Wolfe, et al. "Inhibitory Grids and the Assignment Problem," IEEE Transactions on Neural Networks, March 1993.