Citation
Solving the task scheduling problem using neural networks

Material Information

Title:
Solving the task scheduling problem using neural networks
Creator:
MacMillan, James M
Publication Date:
Language:
English
Physical Description:
x, 149 leaves : illustrations ; 29 cm

Subjects

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

Notes

Bibliography:
Includes bibliographical references.
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Electrical Engineering.
Statement of Responsibility:
by James M. MacMillan.

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:
26882430 ( OCLC )
ocm26882430
Classification:
LD1190.E54 1992m .M35 ( lcc )

Full Text
SOLVING THE TASK SCHEDULING PROBLEM
USING NEURAL NETWORKS
by
JAMES M. MACMILLAN
B.S., University of Nebraska Lincoln, 1980
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
1992
A


This thesis for the Master of Science
degree by
James M. MacMillan
has been approved for the
Department of
Electrical Engineering
by
Jbuglas A. Ross
Date *7 /*? /


MacMillan, James M. (M.S., Electrical Engineering)
Solving The Task Scheduling Problem Using Neural Networks
Thesis directed by Associate Professor William J. Wolfe
ABSTRACT
Solving scheduling problems is one of the fastest growing fields in discrete
optimization and applied combinatorics. The need for fast, efficient algorithms is
understandable from managing a production facility to allocating spacecraft
resources, scheduling problems pervade industry and engineering. The major obstacle
to finding such an algorithm is that scheduling problems are NP-complete; thus,
finding the optimal solution becomes intractable as the problem size grows.
This thesis investigates the application of a unique parallel processing
paradigm to the task scheduling problem. Called neural networks from its similarity
to the brain, this paradigm is based on a network of highly interconnected, simple
processors. Each processor operates independently using local information only.
The premise of this thesis is that the scheduling problem may be reduced to
simpler problems, neural networks can be found to solve these simple problems, and
these networks may be combined to solve the original, complex problem. Indeed, the
scheduling problem posed in this thesis is easily reduced to three simpler problems -
the k-winner, knapsack, and k-contiguous winner problems. Networks to solve the
k-winner and k-contiguous winner problems have been discovered by other
researchers, and are described in this thesis. However, the network to solve the
knapsack problem is novel, and an approach, dubbed dynamic analysis, is used to
m


design a viable network to solve this problem. A simple methodology to combine the
networks is proposed in this thesis. Simulation of the resulting network shows
promising results.
This abstract accurately represents the content of the candidate's thesis. I recommend
its publication.
IV


DEDICATION
For Mary, Michael and Tina. Enough said; I'll show my appreciation for their love
and support through hugs, kisses, smiles and laughter.


CONTENTS
CHAPTER
1 INTRODUCTION...................................................... 1
Problem Description ...........................................3
Notation ...................................................4
Problem Formulation.........................................4
Neural Networks .............................................. 7
Units.......................................................8
Architecture ............................................ 10
Programming .............................................. 14
Strategy .................................................... 15
Problem Reduction......................................... 15
Neural Network Implementation..............................16
Thesis Organization....................................... 17
2 RESOURCES ....................................................... 18
Problem Formulation ......................................... 18
K-Winner Network .............................................20
Finding Minimum Activation Bound Stability Analysis......21
Finding The Minimum Activation Bound Dynamic
Analysis ..................................................23
Solution Characteristics...................................26
Modified K-Winner Network.....................................27
Finding The Bias Dynamic Analysis........................28
Summary ......................................................30
3 COSTS ............................................................32
vi


CHAPTER
Problem Formulation .......................................32
Knapsack Network ..........................................34
Finding Connection Weights And Bias Energy Function
Analysis ...............................................35
Finding Connection Weights Dynamic Analysis ..........39
Simulation Results ..:.....................................53
Summary ...................................................61
4 TASK DURATION .................................................63
Problem Formulation .......................................64
K-Contiguous Network ......................................65
Finding The Bias Stability Analysis ..................67
Simulation Results.........................................69
Summary ...................................................72
5 SCHEDULING PROBLEM ............................................74
Problem Formulation........................................74
Scheduling Network.........................................76
Simulation Results.........................................79
Summary ...................................................88
6 CONCLUSION ....................................................91
REFERENCES................................................... 94
A PROGRAM LISTINGS...............................................96
vii


FIGURES
FIGURE
1-1 Generic Unit....................................................... 9
1-2 Network Architectures............................................. 11
1- 3 Understanding Constraint Satisfaction.............................. 13
2- 1 K-WinnerNetwork ................................................... 21
2-2 K-Winner Hyperplanes .............................................. 24
2-3 K-Winner Dynamics ................................................. 25
2-4 Effect Of Changing The Minimum Activation ....................... 26
2-5 Convergence Regions Of The K-Winner Network ....................... 28
2-6 Modified K-Winner Network...............................:............ 29
2- 7 Effect Of Changing The Bias........................................ 30
3- 1 Knapsack Network................................................... 35
3-2 Energy Function Analysis Solution Characteristics With Self
Connection....................................................... 37
3-3 Energy Function Analysis Solution Characteristics Without Self
Connection....................................................... 38
3-4 Target Plane And Target Region..................................... 40
3-5 Another View Of The Target Plane And Target Region................. 41
3-6 Gradient Descent Flow Field For The Knapsack Network .............. 43
3-7 Dynamic Analysis Solution Characteristics (saddlepoint at sc,
Xp=-1, A,a varied)............................................... 46
3-8 Dynamic Analysis Solution Characteristics (saddlepoint at sc,
Xa=l, varied) ................................................... 47
VIII


FIGURE
3-9 Dynamic Analysis Solution Characteristics (saddlepoint at sa,
^p=-l, Xa varied)................................................... 49
3-10 Dynamic Analysis Solution Characteristics (saddlepoint at sa,
A,a=l, varied) ..................................................... 50
3-11 Knapsack Network Simulation Results (n=4, saddlepoint at sc,
1, Xa varied)................................................... 55
3-12 Knapsack Network Simulation Results (n=4, saddlepoint at sc,
A,a=l, varied) ..................................................... 56
3-13 Knapsack Network Simulation Results (n=4, saddlepoint at sa,
Ap=-1, Xa varied).................................................... 57
3-14 Knapsack Network Simulation Results (n=4, saddlepoint at sa,
X,0=l, A,p varied) .................................................. 58
3- 15 Knapsack Network Simulation Results (n=10, saddlepoint at sc,
A,a=l, varied) ..................................................... 60
4- 1 K-Contiguous Winner Network............................................ 66
4-2 K-Contiguous Winner Network Feasible Solution ........................... 68
4-3 K-Contiguous Winner Network Simulation Results (n=10, k=3,
a varied)............................................................ 70
4- 4 K-Contiguous Winner Network Simulation Results (n=10, k=5,
a varied)............................................................ 71
5- 1 Scheduling Network..................................................... 77
5-2 Scheduling Network Simulation Results Equal Costs And Equal
Durations ........................................................... 80
5-3 Scheduling Network Simulation Results Equal Costs And
Various Durations ................................................... 81
IX


FIGURE
5-4 Scheduling Network Simulation Results Various Costs And
Equal Durations ................................................. 82
5-5 Scheduling Network Simulation Results Various Costs And
Various Durations (I)............................................ 83
5-6 Scheduling Network Simulation Results Various Costs And
Various Durations (II) .......................................... 84
5-7 Scheduling Network Simulation Results Various Costs And
Various Durations (III) ......................................... 85
5-8 Example Of A Non-Feasible Solution (I) ........................... 88
5-9 Example Of A Non-Feasible Solution (II)........................... 89
5-10 Example Of A Non-Feasible Solution (III).......................... 90
x


CHAPTER 1 INTRODUCTION
Solving scheduling problems is one of the fastest growing fields in discrete
optimization and applied combinatorics (Syslo, Narsingh, & Kowalik, 1983). It is
easy to understand why from managing a production facility to allocating spacecraft
resources, scheduling problems pervade industry and engineering.
Formally, scheduling problems are those where an optimal processing order
of tasks (a schedule of tasks) is desired given a set of resources, and subject to
constraints on the tasks, resources and their mutual relationships (Syslo et al., 1983).
A solution is optimal if the schedule maximizes or minimizes a performance measure
without violating the constraints. For example, the production facility mentioned
above may measure performance in terms of profits or delivery time, and the
constraints may include the fabrication sequence, the number of machines, available
personnel, etc.
Scheduling problems are NP-complete; thus, finding the optimal solution
becomes intractable as the problem size grows. Algorithmic methods to find solutions
include mathematical, dynamic, and heuristic programming (White, 1985). The first
two methods, mathematical (e.g., linear programming) and dynamic (based on a
sequence of decisions) programming, guarantee an optimal solution if one exists, but
are costly in terms of computation. Heuristic programming trades the guarantee for
an optimal solution for computational speed.1 However, the heuristics used in this
method are oftentimes unjustifiable, and may preclude optimal solutions in novel
1 For most engineering applications, a solution that satisfies the constraints and is
near optimal is acceptable.


situations. All three methods suffer the same ailment: the amount of computation
grows exponentially as the problem grows. For very large problems, the computation
becomes prohibitive in terms of computational resources and timeliness of the result.
An obvious way to reduce the computation time is to use parallel distributed
processing; that is, interconnected processors executing portions of the algorithm
simultaneously or in parallel. Intuitively, with more processors tackling the problem,
fewer operations are performed by each processor, allowing simpler, and faster,
processors to be used. If taken to the extreme, a solution may be found with a
network of many simple processors, each performing similar operations.
Neural networks, so named for the similarities with the human brain, are a
paradigm for massively parallel networks of simple processors. Although there are
many models, neural networks have the following characteristics ("What are neural
networks, anyway?", 1990):
Computational power is achieved through large numbers of interconnected
simple processors.
The processors operate autonomously. That is, all information required for
operation is available locally, eliminating the need for additional processors to
control the network.
The overall program executed by the neural network resides in the connection
weights between processors, a bias connection to a processor, and the update
rule of the processor.
The application of neural networks to scheduling problems is the main focus of this
thesis.
2


Problem Description
To establish a framework to describe the scheduling problem, a
manufacturing facility, or factory, is the model for discussion. Contained within the
factory are a variety of resources (machines) on which tasks (jobs) are performed in
order to manufacture a product. In general, each task may consist of subtasks
(subjobs or operations) that must be completed in a specific sequence, with each
subtask requiring a different resource type. However, to simplify the problem for this
thesis, tasks have a single operation and require a single resource of a specific type.
Tasks have the following characteristics:
As mentioned above, a resource requirement.
A duration; i.e., the number of time intervals required to perform the task.
A cost of performing the task per time interval. Cost can be thought of as a
burden on a resource shared by all tasks (e.g., labor).
A priority; i.e., if not all tasks can be scheduled, higher priority tasks take
precedence over lower priority tasks.
A time interval preference. The preference is a measure of the desirability of
performing the task during a time interval.
The factory is characterized by:
The number and type of resources available at each time interval.
An allowable range, about a target value, of total cost for each time interval.
If the total cost is too much greater than the target value, then the resource
3


shared by all tasks is stressed. If the total cost is too much less than the target
cost, then that resource is under utilized.
A desirable schedule of tasks would maximize use of the available resources while
scheduling the tasks during preferred time intervals, yet not violate the total cost
range and the priority order of task constraints.
Before formalizing the description of this scheduling problem, the
mathematical notation used throughout this thesis follows.
Notation
Conventions used throughout this document are:
Vectors. Bold, lower case letters denote a vector (e.g., a or b). A subscript on
a vector name, in plain type, identifies an element of that vector (e.g., at is
the i* element of a).
Matrices. Bold, uppercase letters represent matrices (e.g., M or W). A pair of
subscripts on a matrix name, in plain type, identifies an element of that matrix
(e.g., Wtj is the element in the i* row, j* column of W).
Scalars. Upper and lowercase letters, in plain type, denote a scalar.
Problem Formulation
The formulation of the scheduling problem for the factory described above
consists of constraints and objective functions. The constraints define a feasible, or
4


acceptable, solution. The objective functions define the goals of solving the problem,
and identify the optimal, or best, solution. The constraints of the problem are:
The effort applied to a task when scheduled to be performed during a time
interval is fixed. That is, partial or additional effort cannot be scheduled
causing a corresponding increase or decrease in task duration. Formally:
subject to: xit = 0 or 1
where: x,=l if task i is scheduled for time t, 0 otherwise
The time intervals allocated to a task must be contiguous and equal to the
duration of the task. Formally:
subject to: m 'Lxu = di t= i m-\ 2 dj \ t= 1
where: di is the duration, in time intervals, of task i
m is the number of time intervals in the time span
Tasks cannot share a resource dining the same time interval. In general,
different resources may be available at different time intervals. However, to
simplify the problem, all resources are available during all time intervals.
Formally:
subject to: 2 f gXjt ^ Rj i=l
where: ri} = 1 if resource j is required by task i, 0 otherwise
5


Rj is the number of resources of type j
n is the number of tasks
The sum of the costs of all tasks scheduled during a time interval must lie
within a range about a target value. In general, the target value and bound
may vary with the time interval. Again, to simplify the problem, the target
value and bound are the same for all time intervals.
subject to: Te< X CiXu < T+e =i
where: T is the target value
e is the allowable bound about the target
The objectives functions are: value
Maximize resource usage. Formally:
maximize: n I m SIX ryXi, p=i j=1 (=i
where: / is the number of resource types
Maximize the scheduling of highest priority tasks. Formally:
maximize: n m X X PiXu pi t=l
where: pt is the priority normalized by the duration of the task
Maximize the scheduling of tasks during periods of highest preference.
Formally:
6


maximize:
n m
2 2 Q itXft
i= 11= 1
where: qit is a measure of the preference (hereafter,
simply called preference) of performing task
i at time interval t
The constraints and objective functions described above are a simplistic
description of the scheduling of resources in a factory. This formulation ignores
issues such as task sequencing and constraints between resources. Yet, the problem
posed is interesting in that it contains pieces of real-world problems, and offers a
challenge to solve with a neural network.
Neural Networks
As mentioned earlier, neural networks are a paradigm for parallel distributed
processing that is modeled after the human brain. Some of the features of the brain
captured by neural networks are (Mozer, 1990):
Very large numbers of neurons. The human brain contains 1010 to 1011
neurons. (A neuron is referred to as a unit in neural networks).
Neurons receive input from a large number of other neurons. In the cortex,
neurons receive input from 104 other neurons.
Neurons communicate through excitation or inhibition.
Learning or programming involves modifying connection weights to affect
the ability of a neuron to excite or inhibit another neuron.
7


No central controlling processor.
Neural networks are classified in three ways: by the type of unit, the architecture of
the network, and the method that the network is programmed.
Units
Generically, units receive inputs from three sources: connections from other
units, a self connection, and a bias (Figure 1 1). The unit modulates the inputs by
the connection weights, and sums the results to form the net input.
net ft) = £ Wijdj{i) + bi
M
where: net-, is the net input into unit i at time t
Wy is the connection weight from unit j to
unit f, Wu is the self connection weight
aft) is the output or activation value of unit
j at time t
b{ is the bias input into unit i
n is the number of units in the network
t is time
The output state of the unit, called the activation value, is a function of the net input
into the unit. That is,2
2 This formulation assumes that the unit updates in discrete time steps rather than
continuously. Although both are possible, the former represents a more accurate
8


Figure 1-1 Generic Unit
di(t+1) =j[neti(t))
The function finetfi)) is called the activation function or update rule, and describes
the behavior of the unit. Common activation functions include (Mozer, 1990):
Sigmoid or logistic function:
Binary threshold:
fix) = 1, if x > 0
f[x) = 0, if x < 0
Linear:
Ax)=x
model of the computer simulations used in this thesis.
9


Linear threshold:
/(jc) = 1, if a: < 1
fix) =x, if 1 f{x) = 1, ifx> 1
A much more interesting update rule, known as interactive activation
(Rumelhart & McClelland, 1986), is a function of both the net input and the current
activation of the unit:
di(t+1) = ai(t)+r\neti(f)[_M-a;(r)], if neti{t) > 0
fl/(f +1) = a,(f) +r\neti{t)\_ai{t) /], if neti(t) < 0
where: M is the maximum activation bound
m is the minimum activation bound
Tj is the step size
The [M- a,(t)] and [a,(r) m] calculations push the activation of the unit to either the
maximum (M) or the minimum (m) activation values.
The choice of update rule is dependent on the function of the neural network,
the architecture, and how the network is programmed.
Architecture
There are two basic network architectures (Figure 1 2): feed-forward and
recurrent. Feed-forward networks flow activation in a single direction; i.e., the
outputs of a layer of units are the inputs of the next layer. Inputs are presented to the
10


Figure 1-2 Network Architectures
Arrows represent connections. Not all connections, self connections and biases are
shown for clarity.
network by initializing the activations of the input layer of units. After the activations
have propagated through the network, the activations of the output layer of units
represent the output. Therefore, feed-forward networks map an input vector to an
output vector of activations.
Conversely, recurrent networks flow activation in all directions allowing
feedback or closed loops. The initial activation of all units represents the input to the
network. Similarly, after the network has settled, the final activation of all units
represents the output. Dynamically, recurrent networks settle, or relax, to an
11


equilibrium state that satisfies the constraints defined by the weights.3
To understand how weights create constraints, consider a two unit network
that have an update rule with bounded activations (Figure 1-3). Positive connection
weights between the two units indicate a desire for both units to be at the same state.
That is, if the source unit has a positive activation, then the receiving unit is excited
(the net input is positive causing the activation to become more positive). If the
source unit has a negative activation, then the receiving unit is inhibited (the net input
is negative causing the activation to become more negative). Conversely, negative
connection weights indicate a desire for both units to be at opposite states. If the
source unit has a positive activation, then the receiving unit is inhibited; if the source
unit has a negative activation, then the receiving unit is excited. Connection weights
of opposite signs may cause the activations of the two units to oscillate, or converge
to an intermediate state where the net input into each unit is zero.
The above discussion introduces the concept of stability. A stable unit will
remain at the same activation, either at the upper or lower bound defined by the
update rule, or at an intermediate value. The criteria for stability are:
The net input to a unit is zero. In this case, the unit's activation will remain at
a value between the bounds.
Or, the sign of the net input is the same as the sign of the unit's activation. In
this case, the unit's activation will change until it is equal to one of the
bounds, then remain at this value.
3 Recurrent networks are also known as relaxation or constraint satisfaction
networks.
12


nety > 0 netj < 0 netj > 0
+ aj -> max(a) i__ Oj -> min(a) + _ Oj -> max(a)
Q A (+) (+) C O (+f E

netj > 0 neti > 0 netj <0
a, -> max(fl) a, -> max(fl) a, -> min(a)
netj < 0 netj > 0
+ af -> min(a) - Oj -> max(a)
rK b rK D
+ _
netj < 0 netj < 0
a, -> min(a) as -> min(a)
Figure 1-3 Understanding Constraint Satisfaction
The signs on the connections and inside the unit indicate the polarity of the
connection weight and the unit activation, respectively. Self connections and
biases are not shown for clarity. Networks A D are stable. Network E will
oscillate: The activation of unit i will decrease as the activation of unit j increases.
When the activation of unit i becomes negative, the activation of unit j will begin
to decrease. The activation of both units will decrease until the activation of unit j
becomes negative. This will cause the activation of unit j to begin to increase...
A special class of recurrent networks are those with symmetric weights (i.e.,
Wy = WjJ. This network follows the gradient descent of the energy function:
energyit) = -0.5 £2 a^aft) Wy 2 aj(f)bj
i j j
13


The netjt) calculation of the update rule implements the gradient descent locally at
each unit. Therefore, the network converges to the lowest energy state near the initial
state of the units. Note, this energy minimum is a local minimum; there is no
guarantee that the network will find the global minimum.
Programming
Programming refers to setting or modifying the connection weights between
units so that the network performs something useful. Two techniques exist: learning,
and designing. Learning algorithms have been developed for both feed-forward and
recurrent networks; the design techniques are applicable to recurrent networks only.
Learning algorithms fall into three categories: supervised (with a teacher),
reinforcement (with a critic), and unsupervised (without a teacher) learning (Mozer,
1990). A popular supervised learning algorithm for multi-layer feed-forward
networks is back-propagation. The network learns by presenting an input to the
network, comparing the output with the desired result, then propagating the error
backwards from output to input to make incremental changes to the weights. From a
small set of training data, the neural network learns a distributed representation of
relationships between inputs and outputs, and will use this representation to
generalize novel inputs.
There are three techniques to design a recurrent neural network: energy
Junction analysis, dynamic analysis, and stability analysis. Although a brief
14


description follows, further details of each technique are found in later chapters of
this thesis where each technique is used.
The first technique involves creating an energy function with a set of minima
that represent desired results. Connection weights and biases are extracted from the
net input equation determined by taking the partial derivative of the energy function
with respect to the activation of a unit.
The second technique, dynamic analysis, involves defining a gradient descent
flow field dynamic that describes the desired operation of the network. The
connection weights and biases are determined from the eigenvectors and eigenvalues
of the flow field.
Lastly, stability analysis involves analyzing desirable and undesirable states of
the network to determine the network parameters that make the desirable states
stable, and the undesirable states unstable.
Strategy
The overall strategy to find a neural network solution to the scheduling
problem described above is to divide the problem into smaller pieces, find a neural
network solution for each piece, then combine the networks into a single network.
Problem Reduction
To divide the scheduling problem into several simpler optimization problems,
consider two microscopic views of the problem: scheduling multiple tasks during a
15


single time interval; and scheduling a single task over multiple time intervals. In the
former case, two smaller problems arise from the resource and cost constraints:
Resources. Schedule the highest priority tasks such that the number of
resources in use is maximized without exceeding the number of available
resources.
Costs. Schedule the highest priority tasks such that the sum of the costs of the
scheduled tasks is within the acceptable range about the target value.
Scheduling a task over multiple time intervals involves a single problem based on the
task duration constraint:
Duration. Schedule the task during the period of highest preference such that
the time intervals selected are contiguous and the total time is equal to the
task duration.
These three problems encompass all of the constraints and objective functions
identified for the scheduling problem.
Neural Network Implementation
Recurrent networks, with symmetric weights and units that use the interactive
activation update rule, is the neural network architecture that will be studied to solve
the resource, cost and duration constraint problems. Recurrent networks, combined
with the interactive activation update rule, have several characteristics that make this
combination useful to solve discrete optimization problems. Mentioned earlier, these
features are:
16


Gradient descent. The network follows the gradient descent of a well
understood energy function.
Comer seeking. The update rule forces unit activations to migrate to the limits
imposed by the update rule. Therefore, solutions are represented by the final
state of the network, where all units are at the minimum and maximum
activation values.
This network seeks the lowest energy solution near the initial starting state of the
network. By mapping the solutions of the network to possible solutions of the
optimization problem, the energy function of the network encodes the constraints of
the problem, and the initial state of the network represents the objective function.
Thesis Organization
The organization of this thesis agrees with the strategy outlined above:
Chapters 2, 3 and 4 investigate neural network solutions to the resource, cost and
duration problems, respectively. Chapter 5 combines the networks used to solve the
cost and duration constraint problems into a single network. Lastly, Chapter 6
concludes with a discussion of suggested avenues of further research.
17


CHAPTER 2 RESOURCES
Resources represent a hard limit on the number of tasks that may be
performed simultaneously. For example, suppose that a factory has R machines of a
particular type available. If n tasks requiring the use of this type of machine are to be
performed, and n > R, then the upper limit on the number of tasks that may be
scheduled simultaneously is R. Task priority resolves the question of which of the
tasks are scheduled for a given time interval the R tasks with highest priority. Or,
expressed another way, the combination of R tasks that yields the greatest sum of
priorities is scheduled. Note that the maximization of total priority has a desirable
side effect all resources are in use.
Problem Formulation
The problem described above may be defined as follows:
find: x,
maximize: n 'LpiXi i= 1
n /
maximize: £ £ ryXi t=l/=l
subject to: £ rjjXi < Rj i= 1
where: xt =1 if task i is scheduled, 0 otherwise
Pi is the priority assigned to task i


ri} =1 if resource j is required by task i, 0 otherwise Rj is the number of type j resources available n is the number of tasks / is the number of resource types
The first objective function maximizes the sum of the priorities which, as
mentioned above, ensures that all resources are utilized to the maximum extent
possible. The second objective function, which seeks to maximize the number of
resources in use, is redundant; Therefore, the problem formulation is simplified to:
find: *.
maximize: £ PiXi r=l
subject to: rt L ryx, = Rj i= 1
The problem is further subdivided by grouping tasks by resource type, and
solving each individually. The problem becomes:
find:
maximize: £ PiXi i=l
subject to: =R i= 1
Called the k-winner problem, this problem will be the focus of the remainder of this
chapter.
19


K-Winner Network
Fortunately, the k-winner problem has already been solved using neural
networks (Wolfe et al., 1991). This network converges to a solution where £ units are
at maximum activation, and the remaining are at minimum activation. Additionally,
the solution maximizes the sum of initial activation of the k winning units.
The architecture, shown in Figure 2 1, is a fully connected, recurrent
network with symmetric weights, and units that employ the interactive activation
update rule. Key network parameters are:
Wjj = -l, i*j All connections between units are inhibitory
Wu=0 No self connections
bf=0 No bias
k
m =------- The minimum activation bound of the
n-k
update rule, k is the number of winners; n is
the number of units
M= 1 The maximum activation bound of the
update rule
These parameters were derived by setting the weights, bias, and maximum activation
bound to the values shown above, then finding the minimum activation bound using
stability analysis and dynamic analysis.
20


Figure 2-1 K-Winner Network
K-winner neural network architecture described by Wolfe et al. (1991). The units
employ the interactive activation update rule with the activations bounded between
-k/(n-k) and 1, where n is the number of units in the network.
Finding Minimum Activation Bound Stability Analysis
Stability analysis involves selecting a value of a parameter, in this case the
minimum activation bound, that guarantees that feasible, or desirable, solutions are
stable and all others are not. To begin, consider a k-winner network that has
converged to a feasible solution. The net input into a unit at maximum activation is:
neti=-{k- \)-m(n-k),ai = 1
21


In order for these unit to be stable (i.e., remain at maximum activation), the net input
must be nonnegative. Therefore, a constraint on the minimum activation bound must
be:
m <
£+1
n-k
The net input into units at minimum activation is:
netj = -k-m(n -k-\),aj = m
For these units to remain stable (i.e., remain at minimum activation), the net input
must be non-positive. Therefore, the minimum activation bound is constrained by:
Next, assume that the network has converged to a solution with k+1 units at
maximum activation. To make this solution unstable and tend towards a feasible
solution, the units at maximum activation should be unstable, and those at minimum
activation should be stable. Forcing the net input into units at maximum activation to
be negative results in the constraint:
Analysis of the net input to units at minimum activation does not add a constraint.
Lastly, assume that the network has converged to a solution with k-1 units at
maximum activation. In this case, the units at minimum activation should be unstable
so that the network tends towards a feasible solution. Forcing the net input of units at
minimum activation to be positive results in yet another constraint:
m <------
n-k
22


Therefore, the constraints on the minimum activation bound are:
-k
n-k-1
-k+1
n-k
Any value of the minimum activation bound within this range yields a stable, feasible
solution. However, the choice of m = has an interesting geometric interpretation
as well.
Finding The Minimum Activation Bound Dynamic Analysis
The n units, with bounded activations, define an n-dimensional hypercube
with comers that represent all possible solutions of the network. The hypercube may
be thought of as a set of n-1 parallel, n-1 dimensional hyperplanes that are
perpendicular to the diagonal of the hypercube ( a1=a2=...=an) (Figure 2 2). These
hyperplanes, called k-winner hyperplanes (where k ranges from 1 to n-1), contain the
comers with k units at maximum activation and all other at minimum activation. One
of these hyperplanes contains all feasible solutions to the k-winner problem.
The gradient descent dynamics of this network, defined by the eigenvectors
and eigenvalues of the weight matrix, push the network along the axis of flow
towards an asymptotic hyperplane that contains the origin (Figure 2 3). The axis of
flow is defined by a single eigenvector, parallel to the diagonal of the hypercube,
with a negative eigenvalue. The remaining n-1 eigenvectors, with positive and equal
eigenvalues, span the asymptotic hyperplane.
The saddlepoint is the point were the asymptotic hyperplane intersects the
axis of flow (at the origin). At this point, the magnitude of the gradient descent in all
23


Figure 2-2 K-Winner Hyperplanes
The n-dimensional hypercube defined by the unit activations (n=4 shown). The
hypercube can be thought of as a set of n-1 parallel k-winner hyperplanes
perpendicular to the diagonal (a,=a2=...=aj. Each k-winner hyperplane contains
all corners that have k units at maximum activation, and all others at minimum.
directions parallel to the asymptotic plane are equal. That is, the net input into the
units is 0.
Significantly, the asymptotic hyperplane is parallel to the k-winner
hyperplanes. Therefore, for the network to converge to a feasible solution, it is
necessary to align the asymptotic hyperplane with the desired k-winner hyperplane.
The method explored in Wolfe et al. (1991), and reflected in the network parameters
given above, is to change the value of the minimum activation bound (m). Decreasing
m stretches the hypercube such that k-winner hyperplanes move in, then out of,
24


Figure 2-3 K-Winner Dynamics
Examples of the gradient descent flow field defined by the eigenvectors and
eigenvalues of the weight matrix. The axis of flow is along the diagonal
(a,=a2=...=aj. The asymptotic hyperplane contains the origin, is perpendicular to
the axis of flow, and is parallel to the k-winner hyperplanes.
alignment with the asymptotic hyperplane (Figure 2 4). If m=0 and M= 1, then the
hyperplane that defines the feasible solutions is given by:
TLai = k
i
Moving this plane in alignment with the asymptotic plane changes the equation to:
Ea,=0
i
When the network has converged, k units will be at maximum activation; n-k units
will be at minimum activation. Therefore:
kM +(n- k)m = 0
Hence the relationship m = when M= 1.
25


Figure 2-4 Effect Of Changing The Minimum Activation
Making the minimum activation more negative moves the k-winner hyperplanes
into, then out of, alignment with the aymptotic hyperplane of the flow field. The
corners of the k-winner hyperplane aligned with the asymptotic hyperplane
represent feasible solutions and are stable.
Solution Characteristics
The k-winner network finds the solution with the greatest sum of the initial
activation of the k-winning units. This characteristic of the network is due to two
features:
The comers within the feasible k-winner hyperplane are uniformly distributed
and equidistant from the saddlepoint.
The eigenvectors with positive, equal eigenvalues that span the asymptotic
plane are orthogonal.
26


These attributes combine to divide the hypercube into uniform, symmetrical regions,
one for each feasible comer, such that if initialized to a point anywhere within that
region the network will converge to the same feasible comer (Figure 2 5). The
effect is that the network converges to the closest comer to the point of initial
activation. If initialized on the boundary between regions, the network will not
converge to a comer, but will converge to a point on the face of the hypercube.
Also of interest is that the comers within each k-winner hyperplane have
equal energy, where energy is defined as:
energy = -0.5 X X fl,a/ Wy X atb\
i j i
Therefore, the feasible comers have equal energy, and also have the lowest energy of
all comers. Feasible comers with equal energy is indicative of the bifurcation of the
hypercube into symmetric regions that guarantee that the network will converge to
the closest feasible comer.
Modified K-Winner Network
In order to combine networks to solve the scheduling problem, it is necessary
to keep the minimum and maximum activation bounds (m and M, respectively) the
same for all networks. For commonality, the minimum activation bound shall be 0,
and the maximum activation bound shall be 1. These new parameters require that the
k-winner network discussed in the previous section be modified. Fortunately, a
parametric duality exists between the bias and the minimum activation bound (Wolfe
27


Figure 2-5 Convergence Regions Of The K-Winner Network
The combined effect of the orthogonal eigenvectors, with equal and positive
eigenvalues, that span the asymptotic plane, and the uniform distribution of
comers within the k-winner hyperplane is to divide the hypercube (n-3 shown)
into uniform regions from within which the network will always converge to the
same feasible solution. This results in the network converging to the closest
feasible corner.
et al., 1991). Therefore, given network shown in Figure 2-6, the approach will be to
find a bias that makes the feasible solutions stable.
Finding The Bias Dynamic Analysis
Rather than moving the k-winner hyperplanes by changing m, the asymptotic
hyperplane can be moved by changing the bias (Figure 2-7). Moving the asymptotic
28


W -W =-l
"in "nl 1
Figure 2-6 Modified K-Winner Network
Modified k-winner network where the minimum and maximum activations are 0
and 1, respectively. The bias shifts the asymptotic plane of the flow field into
alignment with the k-winner hyperplane.
plane requires that the saddlepoint be moved from the origin along the diagonal of
the hypercube until it lies in the desired k-winner hyperplane. In this plane:
Ea, = k
I
Therefore, the saddlepoint (s) is located at:
Recall that at the saddlepoint the net input into the units is 0:
netj = 2 WySi = 0
j
-(fi-l)|-+b, = 0
Therefore:
29


Figure 2-7 Effect Of Changing The Bias
Changing the bias shifts the asymptotic hyperplane of the flow field into, then out
of alignment with the k-winner hyperplanes.. When the asymptotic hyperplane is
aligned with a k-winner hyperplane, then the corners in that hyperplane are
feasible solutions and are stable.
bi =
kin-1)
This result is consistent with the stability analysis performed by Wolfe et al. (1991)
which showed that:
k- \ Summary
Mapping the resource allocation problem to the k-winner network is straight
forward. Units represent tasks; k represents the number of available resources. The
30


final activation value of the unit determines if the task has been scheduled; a unit at
maximum activation symbolizes a scheduled task. Priorities are represented as the
initial activation of the units. The greater the priority, the greater the initial activation
value (but bounded between the minimum and maximum activation).
31


CHAPTER 3 COSTS
The cost of performing a task represents a burden on a resource. The total cost
of all tasks to be performed should not be so great that the resource is stressed, nor
should it be so little that the resource is underutilized. Therefore, the total cost should
be within some bound around a target value, where the target value represents a
balanced workload.
As an example, suppose that the cost associated with a task is the amount of
labor required to perform that task during a time interval. Given a fixed staff, the best
solution would be to schedule those tasks whose total cost is equal to the staff size.
Minor perturbations in staffing may be tolerated by an organization through overtime
in the under staffed case, or loaning out employees to other organizations in the over
staffed case. At the extremes, scheduling all tasks may strain the staff to the point that
tasks are not completed; conversely, scheduling too few tasks may result in layoffs.
The bound about the target value defines the feasible or acceptable solutions
(solutions that do not violate the constraints). As in the previous chapter, task priority
serves as the objective function; i.e., the feasible solution with the greatest sum of
priorities is optimal.
Problem Formulation
The problem described above may be formulated as:
find:
x,


maximize:
n
£ PiXi
r=l
subject to: T-e < E c,*,- < T+e
j=i
where: xt =1 of task / is scheduled, 0 otherwise
pt is the priority assigned to task i
c; is the cost of performing task i; costs are
nonnegative
T is the target total cost
e is the allowable bound about T
n is the number of tasks
This problem is very similar to the knapsack problem described in operations
research texts (Syslo et al., 1983). Knapsack problems derive their name from
packing a knapsack; that is, given items with a survival value and a weight, pack the
knapsack in such a fashion that the total survival value is maximized (the objective
function) without exceeding a total weight threshold (the constraint). Variations to
this problem include the 0-1 multidimensional knapsack problem where the number
of an item is bounded to 0 or 1 (as opposed to being unbounded where any number of
an item may be selected), and multiple constraints must be satisfied. The problem
formulated above is most similar to this variation, but will be referred to simply as
the knapsack problem.
33


Knapsack Network
The neural network used to explore the knapsack problem is a fully
connected, recurrent network with units that apply the interactive activation update
rule (Figure 3 1). Per the convention established in the previous chapter, the
minimum and maximum activation bounds (m and M) are fixed at 0 and 1,
respectively. Unlike the k-winner network, a neural network approach to this problem
has not been previously found, so both the weights and biases have to be derived.
Note that the network is not constrained to be symmetric.
Based on the k-winner network, the knapsack network should have the
following characteristics:
Solutions are network states where the units are at either minimum or
maximum activation.
Feasible solutions are stable.
Non-feasible solutions are unstable.
Feasible solutions have the lowest energy.
Feasible solutions with the same total cost have the same energy.
Dynamics push towards the closest feasible solution.
34


Figure 3-1 Knapsack Network
The network used to explore the knapsack problem. Note that the connections are
not constrained to be symmetric; i.e., Wtj does not have to equal Wjr
Finding Connection Weights And Bias Energy Function Analysis
A classical method of designing a network is to begin with an energy function
that represents the problem to be solved (Hopfield & Tank, 1985). The minima of
this energy function should be the desired solutions. Ignoring the bound parameter e
for a moment, an energy function appropriate for this problem is:
energy(t) = (T-'Lciai(t))2
i
The energy decreases as the total cost, llciai(t), nears the target value T.
i
Differentiating the energy function with respect to the activation of a unit,
aft), yields the net input to that unit:
35


neti(t) = -2c i Z cjaj(t) + 2c iT
j
Weights and biases are determined by comparing this equation to the standard
equation for net input:
neti{t) = Z WijQjit) + bt
j
Therefore, the bias into each unit is:
bi = 2c{T
The connection weights between units are:
Wi, = 2 CiCj, i *j
And, the self connection weights are:
Wii = -2c2i
Note that the weights between units are symmetric; i.e., WtJ = Wjr
A simple test of the validity of these parameters is to examine the energy and
stability of each of the solutions. Those solutions with a total cost at or near the target
value should be stable and should have the lowest energy. The results of an
examination of each solution of a network of four units (n = 4) are shown in Figure 3
- 2. As desired, the lowest energy solutions are those with a total cost equal to the
target value. However, none of the comers are stable, so the network will not
converge to a solution.
Abe (1989) proved that, for connection weights derived in this fashion, the
self connection must be eliminated for the network to have stable comers. To convert
a self connection weight to a term in the bias, an increase in the self connection
36


Figure 3-2 Energy Function Analysis Solution Characteristics With Self
Connection
Energy vs cost of all possible solutions given: n=4, Cj=l, c2=3, c3=2, c4=4 and
T=3 (normalized values were used in the calculations; i.e., Cj=0.183, c2=0.548,
c3=0.365, c4=0.73 and T=0.548). Derived from differentiating the energy function
with respect to a unit activation, the connection weights and biases include a
nonzero self connection weight.
weight of a is equivalent to a decrease in bias by a/2. This leads to a new set of
connection weight equations:
bi = 2ciT- c2
Wv = -2dCj, i j
W-=0
'it
37


Figure 3-3 Energy Function Analysis Solution Characteristics Without
Self Connection
Energy vs cost of all possible solutions given: n=4, c,=l, c2=3, c3=2, c4-4 and
T=3 (normalized values were used in the calculations; i.e., c,=0.183, c2=0.548,
c3=0.365, c4=0.73 and T=0.548). The self connection weights of the previous
example are eliminated by changing the biases.
Using the same parameters as the previous experiment, examination of the solutions
(Figure 3-3) reveals that three solutions are stable. Two of the solutions have a total
cost equal to the target, have equal energy, and have the lowest energy of all
solutions. The remaining stable solution is one of three solutions that differ from the
target value by the minimum cost. Interestingly, all three solutions have the same
energy, yet only one is stable.
38


A positive attribute of this network is that the energy function is symmetric
about the target value. That is, solutions whose total cost differs from the target by
equal amounts have equal energy. Unfortunately, the stability region is not
symmetric.
Finding Connection Weights Dynamic Analysis
Another approach to designing a network to solve the knapsack problem is to
define the desired gradient descent flow field by specifying the eigenvectors and
eigenvalues of the weight matrix. First, to set the stage, the geometric interpretation
of the network and the problem are provided.
The n units, with activations bounded by m and M, define a ^-dimensional
hypercube whose comers are all possible solutions of the network. Within this space,
the vectors c and a(t) represent costs and activations, respectively. Note that a (the
activation vector without dependence on time) represents any point in the hypercube.
Given that m and M are 0 and 1, respectively, the constraints:
l|c||=l
c- a= T
define a n-1 dimensional hyperplane that cuts through the hypercube (Figure 3-4).
Called the target plane (d^), this hyperplane may intersect several k-winner
hyperplanes (Figure 3-5). Note that this plane is perpendicular to the cost vector c.
The bound about T, e, adds a dimension along c to the hyperplane, creating a n
39


Figure 3-4 Target Plane And Target Region
A 3 dimensional example of the hypercube defined by the unit activations showing
the Target Plane (dT) and the Target Region (dd). Corners within the target
region represent feasible solutions.
dimensional space called the target region {dd) The comers that lie within the
target region satisfy the constraints:
T-e and are the feasible solutions.
The k-winner network (Wolfe et al., 1991) has an eigenvector (e^), with a
negative eigenvalue (A,p), perpendicular to the k-winner hyperplane (coincident with
the diagonal a{=a2= ... =an). The remaining n-1 eigenvectors (ew) form an orthogonal
40


Figure 3-5 Another View Of The Target Plane And Target Region
In this example, the hypercube defined by the unit activations is represented as n-I
parallel k-winner hyperplanes that are normal to the diagonal of the cube
(ai~a2=...=ar). A k-winner hyperplane contains all corners that have k units at
maximum activation and all others at minimum activation. Corners at the
intersection of the Target Region (dfi) and the k-winner hyperplanes are feasible
solutions.
basis that spans the k-winner hyperplane, and have equal and positive eigenvalues
(kj. This creates a symmetric gradient descent flow field that is asymptotic to the
k-winner plane. The saddlepoint (s), where the diagonal of the hypercube intersects
the k-winner hyperplane, is equidistant from all comers within that plane. This
41


guarantees that all feasible comers have equal energy. Additionally, at the
saddlepoint, the net input into each unit is 0.
Using the k-winner network as a prototype, the gradient descent flow field to
solve the knapsack problem has the following characteristics:
The resulting flow field is illustrated in Figure 3-6.
An obvious selection for ep is:
ep = c
The selection of remaining eigenvectors is more difficult. By trial and error, the
following eigenvectors were found for the n = 3 case:
ep||c A,p < 0
A single eigenvector, parallel to the cost
vector, with a negative eigenvalue
eoi c, X,a = 'kaj > 0 n-1 eigenvectors, normal to the cost vector,
with positive and equal eigenvalues
of -L a/> i
The n-\eigenvectors form a normal basis
s lies on <£T
The saddlepoint lies within the target plane
so that the asymptotic plane of the flow
field, defined by the n-1 eigenvectors, is
coincident with the target plane
al t ^2>Cl,0]
And for the n = 4 case:
42


Figure 3-6 Gradient Descent Flow Field For The Knapsack Network
The asymptotic line of the flow field is normal to the Target Plane (d7). The
saddlepoint is located in so that the asymptotic plane of the flow field is
coincident with &There are two choices of saddlepoint: where the projection of c
intersects (^(identified as sc) and the intersection of the hypercube diagonal with
^(called sa).
eo3 = [~C4, C3, -C2, Cl]
The eigenvectors for higher dimensional cases follow the same pattern.
The weight matrix is found by solving the following equations
simultaneously:
Wep = A,pCp
43


Weal \teal
~ ^'aa2
We, = X,e,,
The resulting connection weights are:
Wy = ~^a A.p i *j
These connection weights were verified as solutions for dimensions greater than four.
The selection of a saddlepoint is difficult in that, because feasible solutions
will not necessarily be uniformly distributed, finding a point within df that is
equidistant from the feasible solutions requires knowledge of the location of the
feasible solutions. Of course, once the locations of feasible solutions are known, the
problem is solved. Two guesses at saddlepoints are the intersection of the projection
of c onto <£T and the intersection of the diagonal a1=u2=...=a and & These points,
designated sc and sa, respectively, are:
sc = Tc
s =-^
Sa 2 c,
i
Recall that the saddlepoint is the point on d^where the net input is 0. Therefore, the
bias into a unit is found by solving:
44


Ws + b = 0
At sc, the bias into each unit is:
bi = k$Tci
And at sa:
J
Repeating the experiment of the previous section, Figures 3-7 and 3-8 show
the energy and stability of each comer at various combinations of values of Xa and
with the saddlepoint at sc. From this data, the following observations may be made:
As ka increases, the difference in energy between comers with equal total cost
increases. This difference is 0 when Xa equals 0.
More comers become stable as Xa increases.
As increases the difference between the minimum and maximum energy
comers increases. However, the difference in energy between comers of equal
total cost remains the same.
More comers become unstable as increases.
The total cost of the stable comers are not symmetrically distributed about T.
Comers with equal total cost will not necessarily be stable if one of those
comers is stable.
Comers with equal energy will not necessarily be stable if one of those
comers is stable.
45


Energy
2.5- 1
2.0-
1.5-
1.0-
-1.0-
-1.5
-2.0
-2.5
r H o .5- A - 1 1
u -.5- LZJ 1 1 Ilil' LJU u
Energy 2.5
VO-8
-2.5
m Unstable
I Stable
0 1 2 T 4 5 6 7 8 9 10 Total Cost
. r-i m
. Lid 111
0 1 2 T 4 5 6 7 8 9 10 Total Cost
Figure 3-7 Dynamic Analysis Solution Characteristics (saddlepoint at sc,
Xp=-1, \ varied)
Energy vs cost of all possible solutions given: n=4, c}=l, c2=3, c3=2, c4=4 and
T=3 (normalized values were used in the calculations; i.e., Cj=0.183, c2=0.548,
c3=0.365, c4=0.73 and T=0.548). Weights and biases were derived by crafting the
desired flow field dynamics.
46


Energy
K=0.0
Multiple bars within a single
total cost category indicate that
more than one comer have that
total cost
2.5- i
2.0-
1.5-
1.0-
.5-
0-
-.5-
-1.0-
-1.5-
-2.0-
-2.51
O'
8 9 10
Total Cost
012T456789 10
Total Cost
Energy 2.5 -i
2.0-
1.5-
1.0-
.5-
0-
-.5-
-1.0-
-1.5-
-2.0-
-2.5-1
E3 Unstable
I Stable
V=-8
12T456789 10
Total Cost
Figure 3-8 Dynamic Analysis Solution Characteristics (saddlepoint at sG,
X.a=l, \ varied)
Energy vs cost of all possible solutions given: n=4, c,=l, c2=3, c3=2, c4=4 and
T=3 (normalized values were used in the calculations; i.e., c,=0.183, c2=0.548,
c3=0.365, c4=0.73 and T=0.548). Weights and biases were derived by crafting the
desiredflow field dynamics.
47


Although violations occur, energy decreases as the difference between the
target value and total cost decreases. The number of violations to this rule
decreases as increases.
Repeating the above experiment with the saddlepoint at sa (Figure 3-9 and
Figure 3-10) yields similar observations with the addition of:
The difference in energy between comers with the same total cost is
significantly less than if the saddlepoint were at sc.
This implies that sa is a better approximation to the point equidistant to all feasible
comers than sc.
A strategy to select values for Xa, ^ and s is to assume that the network
converged to feasible and non-feasible comers, then select parameter values that
make those comers stable and unstable, respectively. First, assume that the network is
at a comer where the total cost equals T. The net input into units at maximum
activation is:
Next, assume that the network has converged to a comer with a total cost of T
- Ac. The net input into the units are:
Similarly, the net input for units at minimum activation is:
For this comer to remain stable, the following constraints must be met:
48


Energy 2.5-
2.0-
1.5-
1.0-
.5-
0-
-.5-
-1.0-
-1.5-
-2.0-
-2.5 J-
H Unstable
Stable
V=0-8
2T456789 10
Total Cost
Figure 3-9 Dynamic Analysis Solution Characteristics (saddlepoint at sa,
Xp=-l,X, varied)
Energy vs cost of all possible solutions given: n=4, ct=l, c2=3, c3=2, c4=4 and
T=3 (normalized values were used in the calculations; i.e., Cj=0.183, c2=0.548,
c3=0.365, c4-0.73 and T=0.548). Weights and biases were derived by crafting the
desired flow field dynamics.
49


Energy 2.5 -i
2.0-
1.5-
1.0-
.5-
0-
-.5-
-1.0-
-1.5-
-2.0-
-2.5-1
012T456789 10
Total Cost
Multiple bars within a single
total cost category indicate that
more than one comer have that
total cost
Energy
Xf-4
Energy
V-8
H Unstable
H Stable
Total Cost
Figure 3-10 Dynamic Analysis Solution Characteristics (saddlepoint at
s Xa=l, varied)
Energy vs cost of all possible solutions given: n=4, c,=l, c2=3, c5=2, c4=4 and
T=3 (normalized values were used in the calculations; i.e., c,=0.183, c2=0.548,
c3=0.365, c4=0.73 and T=0.548). Weights and biases were derived by crafting the
desiredflow field dynamics.
50


neu = - A,p jcf(r- Ac)+la+bit at = 1
netj -^a A.p ^Cj(T- Ac) + bj, aj = 0
In this case, units at maximum activation should remain at that state. Therefore, the
net input into these units must be nonnegative, yielding the constraint:
bi ^ Xp jc,-(r- Ac) la
For the units at minimum activation, if c( < 2Ac or cf + 8c = 2Ac, 8c > 0, then the total
cost would be closer to T if this unit were at maximum activation. Therefore, it is
desirable that the net input is positive, which results in the constraint:
bt > (la Xp jcy(r- 0.5(cf + 5c)), 0.5(c/ + 8c) = Ac
Conversely, if cf > 2Ac or c,. 8c = 2Ac, 5c > 0, then the unit should remain at
minimum activation. Therefore, the net input should be non-positive, which yields
the constraint:
bi<
ctf- 0.5(c,- 8c)), 0.5 (d 8c) = Ac
Lastly, assume that the network has converged to a comer with a total cost of
T + Ac. Net inputs into the units are:
netj = -
netj = -
A,p ^
^

Ci(T + Ac)+Xa+bi, at = 1
Cj(T+ Ac)+bj, aj = 0
51


For units at maximum activation, if c( < 2Ac or c( + 8c = 2Ac, then the total score
would be closer to T if this unit were at minimum activation. Therefore, the
constraint on the bias becomes:
bi < - Xp)cf(T+ 0.5(c, + 5c)) Xa, 0.5(cf + 5c) = Ac
For all other cases, the units should remain at the same activation. Therefore,
additional constraints on the bias are:
bt > (xa Xp jc,(r+ 0.5(c,- 8c)) Xa, 0.5(c, 8c) = Ac
bi < ^Xa Xp)c<(T + Ac)
Combining all of the constraints yields the following set of inequalities:
(x Xp^CfT-Xa < bi < (Xa "Xp jc.T
^Xa Xp jcf(r- Ac) Xa (xo-Xp)c,(r-0.5(c, + 5c)) 0.5(c, + 5c) = Ac
(xa Xp )c,(T+ 0.5(c,- 5c)) -Xa 0.5(c,- 8c) = Ac
The best solution that satisfies these inequalities appears to be:
Xa 0
bi = Xp CiT
Note that this places the saddlepoint at sc. Stability and energy analysis of the comers
reveals that, although the feasible comers have lowest energy, none of the comers are
stable (regardless of the value of Xp). This solution is very similar to the weights
52


derived from energy analysis in the previous section (prior to shifting the self
connection weight to the bias). In that case, the eigenvalues were Xp = -2 and Xa = 0,
with the saddlepoint at sc. Again, the feasible comers have lowest energy, but none of
the comers are stable.
Although the results show that this network does not meet all the desirable
characteristics of the knapsack network, the equations for weights and biases provide
parameters (ka, Xp and s) that may be tweaked to obtain the desired or acceptable
performance. These parameters allow the selection of e to define the feasible region
around &
Simulation Results
The knapsack network was simulated on a personal computer using a program
written in Pascal (Appendix A). Because the simulation was run on a single processor
computer, the inherent speed of a neural network was not realized. Regardless, the
simulations were useful to evaluate the performance of the network.
For each simulation trial, the activations of the units were initialized to
random values between 0.25 and 0.75. The network was allowed to run until the
network converged to a solution or 5000 iterations (updates), whichever came first.
Convergence to a solution is defined as when the activations of all units are within
5% of the minimum or maximum activation bound. That is, if, for all i, a,(0) <
0.05 or <2,(0) > 0.95, then the network converged to a solution.
53


Performance of the network was measured by two parameters: total cost and
score. The total cost is defined by:
TotalCost = X 0) where af>>0) = 0 or 1
I
And the score is given by:
Score = X a,(0)a,( 0) where a,(0) = 0 or 1
i
These parameters were compared against the optimal solution, found by a brute force
algorithm, where optimal is defined as the solution with a total cost equal to the
target value having the greatest score. The score was considered relevant only for
those solutions with a total cost equal to the target value.
Figures 3 11, 3 12, 3 13 and 3-14 show the results of simulating the
knapsack network using the examples from the previous section. From the results, the
following observations may be made:
When A,a=0, the network does not converge. This value eliminates the
eigenvectors that span the asymptotic plane so that the network no longer
pushes outward from the axis of flow. Without this push, the network cannot
reach the comers of the hypercube.
As A.a increases, the frequency and magnitude of errors in the total cost of
solutions increases, but the frequency of trials that did not converge decreases.
The converse is true as the magnitude of increases.
Although the examination of comers performed in the previous section
indicated otherwise, the network with the saddlepoint at sc performed better
than the network with the saddlepoint at sa.
54


Count
X=0.0
Count
VO-*
NC -3 -2 -1 T +1 +2 +3
Total Cost
5-
4-
3-
2-
1 -
NC -3 -2 -1 T +1 +2 +3
Total Cost
Count
x=o.s
51
4-
3-
2-
1
NC -3
All Optimal
-2 -1 T +1 +2 +3
Total Cost
Figure 3-11 Knapsack Network Simulation Results (n=4, saddlepoint at
sc, Xp=-1, Xa varied)
The distribution of the total cost of solutions found by the network given the
following: cT=[l,3,2,4], T=3, and initial activations set to random values between
0.25 and 0.75. 'NC' indicates a trial that did not converge to a solution after 5000
iterations, '-x' and '+x' indicate a total cost of T-x and T+x, respectively.
55


Count
Xp=0.0
Count
v-4
5-i
4-
3 -
2-
1 -
NC -3
All Optimal
-2 -1 T +1 +2 +3
Total Cost
Count
\=-8
5-i
4-
3 -
2-
NC -3
All Optimal
-2 -1 T +1 +2 +3
Total Cost
Figure 3-12 Knapsack Network Simulation Results (n=4, saddlepoint at
sc, Xa=l, varied)
The distribution of the total cost of solutions found by the network given the
following: cT=[l,3,2,4J, T=3, and initial activations set to random values between
0.25 and 0.75. 'NC' indicates a trial that did not converge to a solution after 5000
iterations, '-x' and '+x' indicate a total cost of T-x and T+x, respectively.
56


Count
K-o-o
T +1 +2 +3
Total Cost
Count
Xa=0.4
5-i
4-
3-
NC -3 -2 -1 T +1 +2 +3
Total Cost
Count
V=0-8
5-i
4-
3-
2-
1 -
NC -3
All Optimal
I.
-2 -1 T +1 +2 +3
Total Cost
Figure 3-13 Knapsack Network Simulation Results (n=4, saddlepoint at
s Xp=-1, Xa varied)
The distribution of the total cost of solutions found by the network given the
following: cT=[l,3,2,4J, T=3, and initial activations set to random values between
0.25 and 0.75. 'NC' indicates a trial that did not converge to a solution after 5000
iterations, '-x' and '+x' indicate a total cost of T-x and T+x, respectively.
57


Count 5 -i
NC -3 -2 -1 T +1 +2 +3
Total Cost
Count
V-4
All Optimal
I
-2 -1 T +1 +2 +3
Total Cost
Count

All Optimal
I
-2 -1 T +1 +2 +3
Total Cost
Figure 3-14 Knapsack Network Simulation Results (n=4, saddlepoint at
s K=l, \ varied)
The distribution of the total cost of solutions found by the network given the
following: cr=[l,3,2,4], T=3, and initial activations set to random values between
0.25 and 0.75. 'NC' indicates a trial that did not converge to a solution after 5000
iterations, '-x' and +x' indicate a total cost ofT-x and T+x, respectively.
58


All trials that converged to a solution with a total cost equal to the target value
found the optimal solution. Trials that converged to solutions with total costs
greater than the target value also had scores greater than that of the optimal
solution. Conversely, the trial that converged to a solution with a total score
less than the target value had a score less than that of the optimal solution.
Figure 3-15 shows the results of simulations of a larger network (n=10). The results
are consistent with the observations listed above. However, there was one trial that
converged to a solution with a total cost equal to the target value that was not the
optimal solution. The score of this trial was within 99% of the score of the optimal
solution.
The key determinant to network behavior is the ratio of the magnitudes of the
eigenvalues:
A,p
'Ka
The ratio> determines the dominance of the normal (to the target plane) component of
the gradient over the parallel component. The greater this ratio, the more dominant
the normal component of the gradient, and the greater the force that pushes the
network onto the target plane. The effect is that, as the ratio increases, the stable
comers furthest from the target plane become unstable. As the number of the stable
comers decrease, the network has fewer comers to choose as a solution. If a stable
comer does not lie in the direction of the parallel gradient, then the network will
move to and remain on the face of the hypercube.
59


Count
101
8-
*r-i 6
NC T +1 +2 +3 +4 +5 +6
Total Cost
The remaining 6 trials
converged to a
solution with total
costs >T+6
Count
*r-io
Count
X3=-100
10-i
8-
6-
4-
2-
19 trials converged
to optimal solutions
NC T +1 +2 +3
+4 +5 +6
Total Cost
Figure 3-15 Knapsack Network Simulation Results (n=10, saddlepoint at
sc, X=l, varied)
The distribution of the total cost of solutions found by the network given the
following: cT=[l,2,3,4,5,6,7,8,9,10], T=10, and initial activations set to random
values between 0.25 and 0.75. 'NC' indicates a trial that did not converge to a
solution after 5000 iterations, '-x' and '+x' indicate a total cost of T-x and T+x.
60


Summary
The knapsack network is a generalization of the k-winner network. That is, if
the costs associated with each unit are equal, then the target plane is parallel to the
k-winner hyperplanes. Judicious selection of the target value will align the target
plane with one of the k-winner planes.
An interesting outcome of the development of the knapsack network, contrary
to the expectations resulting from the analysis of the k-winner network, is that the
lowest energy solution is not necessarily the optimal solution. In this case, the lowest
energy stable solution along the path of the gradient descent is the optimal solution.
As is the case of the k-winner network, mapping the knapsack problem to this
network is straightforward. Units represent tasks, and the final activations of the units
determine which tasks have been scheduled. A unit at maximum activation
symbolizes a scheduled task. Priorities are represented as the initial activations of the
units. The greater the initial activation, the greater the priority of the task. Lastly, the
allowable bound about the target value is adjustable through the eigenvalues (?ia and
V-
The analysis and simulations briefly evaluated the performance of the
knapsack network. For the purpose of this thesis it is considered sufficient. However,
further work is required to resolve the following issues:
The definition of an optimal solution is unclear if the allowable bound about
the target value in nonzero. Regardless of the bound, the simulation results
61


described above assumed that the solution with a total cost equal to the target
value having the largest score is optimal. Perhaps the solution within the
allowable bound that has the greatest score should be considered optimal.
The statistical performance of the network in selecting the optimal solution is
unknown.
A relationship between the eigenvalues and the allowable bound has not been
formulated.
62


CHAPTER 4 TASK DURATION
The previous chapters have focused on selecting the best set of tasks to be
scheduled within a single time interval given resource (Chapter 2) and cost (Chapter
3) constraints. Conversely, this chapter will concentrate on scheduling a single task of
a given duration within a bounded time span.
Given that the time span is divided into equal time intervals, and that the task
duration is an integer multiple of the time interval, then the problem is to find the set
of contiguous time intervals equal to the task duration that represents the best time to
schedule that task. From this problem statement the constraints are readily apparent:
The duration of the schedule must equal the task duration, and the schedule must
consist of contiguous time intervals.
The objective function is embodied by the phrase best time to schedule. To
provide a framework for this determination, each time interval is assigned a
preference that is a measure of the desirability of performing the task during that time
interval. The best set of contiguous time intervals has the greatest sum of preferences
of the time intervals selected. To better understand preferences, consider the
following example: Assume that the task to be scheduled is to eat lunch. Because
lunch is normally between noon and 1:00 p.m., time intervals within that period have
the highest preference. Although not as desirable, slightly earlier or later lunches are
still acceptable; therefore, time intervals between 11:00 a.m. and noon, and 1:00 p.m.
and 2:00 p.m. have slightly lower preferences. The further a time interval is from the
noon hour, the lower the preference. When a time interval is so far from the noon
hour that it is no longer desirable to consider lunch, then the preference is 0.


Problem Formulation
The problem defined above may be formulated as follows:
find:
m
maximize: £ qdi
r=i
m
subject to:
subject to:
where:
Xti = d
r=l
171-1
£ = d 1
i=l
ts =1 if the task is scheduled during time
interval i, 0 otherwise
q{ is the score assigned to time interval i
d is the duration of the task
m is the number of time intervals in the time
span
The first constraint assures that the duration of the schedule is equal to the task
duration. The second forces the time intervals of the schedule to be contiguous. Note
that this is a non-linear constraint.
This problem is very similar to the k-winner problem (Chapter 2), but with
the additional constraint that the winners are contiguous. Therefore, this problem is
called the k-contiguous winner problem.
64


K-Contiguous Network
The k-contiguous winner network has been explored by Shaw (1991). This
network converges to a solution with k adjacent units at maximum activation, and the
remainder at minimum activation. In general, this network converges to the feasible
solution with the greatest sum of the winning units' initial activations.4
The network used by Shaw (1991) is a recurrent, symmetric network, similar
to those used in the previous chapters (Figure 4-1). The key to this network is the
neighborhood connection weight which defines a neighborhood of width k about a
unit. Units outside the neighborhood are inhibited through a -1 connection weight.
Units within the neighborhood are encouraged through the less negative
neighborhood connection weight. Formally, the weights in the network are:
Wjj = a,mod^|/-j|,n j < ,i
Wy = -1, mod( | i-j |, n j > i *j
Wu = 0
where: a is the neighborhood connection weight
n is the number of units in the network
k is the width of the neighborhood; k must
be odd
4 Depending on the network parameters, Shaw (1991) reported that the network
converged to the optimal solution from 47% to 70% of the trials.
65


Figure 4-1 K-Contiguous Winner Network
The pattern of connections for the k-contiguous winner network is illustrated for a
single unit (n=7, k=5). Those units that are within the neighborhood of the unit
are connected by a weight of a; all others are connected with a weight of -1. This
pattern is repeated with each unit as the center of the pattern. Note that the
connections wraparound the ends of the network.
Note that the connections wraparound the ends of the network. That is, for k=3, the
neighborhood around the last unit includes the first unit. The neighborhood
connection weight is bounded between 0 and -1. If equal to -1, then the network
degenerates into a k-winner network.
Fixing the maximum activation bound to 1 and the bias to 0, Shaw (1991)
experimented with different combinations of values of the neighborhood connection
weight and the minimum activation bound. In order to combine this network with
those developed in the previous chapters, the minimum (tri) and maximum (M)
66


activation bounds must be fixed to 0 and 1, respectively. Therefore, the stability
analysis performed by Shaw (1991) is repeated with these constraints.
The dynamics of this network are much more complicated than the k-winner
and knapsack networks. In this case, the feasible solutions are a subset of the comers
that lie within a single k-winner hyperplane. The network dynamics separate the
comers within the plane so that the feasible comers are stable and all other comers
are not. As in the knapsack network, the feasible comers are not necessarily
symmetrically distributed within the k-winner network. Nor do the feasible comers
form a single subspace within the k-winner hyperplane. Because the eigenvectors and
eigenvalues are not easily depicted, the network parameters are derived using stability
analysis only.
Finding The Bias Stability Analysis
Given that the network has converged to a feasible solution, the stability of
the units on the boundary between those at maximum and minimum activation
represent the limiting case to ensure stability of all units (Shaw, 1991). These units,
identified as A and B in Figure 4-2, have a net input of:
netA =-^-(a-\) + b,aA = 1
netB = -^-(a-\)-\+b,aB=0
For A and B to remain stable (i.e., for A to remain at maximum activation and B to
remain at minimum activation), the net input into A must be nonnegative and the net
input into B must be non-positive. This results in the following bound on the bias:
67


Figure 4-2 K-Contiguous Winner Network Feasible Solution
The conditions that make the units identified as A and B stable ensure that the
remaining units are stable as well.
^-(l-a) Note that if k= 1, there is no longer a neighborhood about a unit and the network
becomes a k-winner network with 1 winner. From Chapter 2, the bias required for
this network to have stable solutions is:
where: n is the number of units
Therefore, the appropriate bias for the k-contiguous winner network is:
b = ^k 1-0)+^-
68


Simulation Results
As was the case for the simulations of the knapsack network, the k-contiguous
network was simulated on a personal computer using a program written in Pascal
(Appendix A). The performance of the network was measured in two fashions: the
frequency that a feasible solution was found, and the score of the feasible solution.
The score of a solution is defined by:
Score = E a,(0)ai( 0) where a(.(0)=0 or 1
i
The score of the solution found by the network was compared against the score of the
optimal solution (found using a brute force algorithm; i.e., the scores of all possible
feasible solutions were' determined and the solution with the greatest score was
selected as optimal).
For each simulation trial, the initial activation of each unit was set to a
random value between 0.25 and 0.75. The network was allowed to run until the
network converged to a solution or 5000 iterations, whichever occurred first. A
solution was found when the activations of all units were within 5% of the minimum
and maximum activation bound. That is, for all i, if a,(0) < 0.05 or fl,(0) > 0.95,
then a solution was found.
Figures 4-3 and 4-4 show the results of simulations with k=3 and fc= 5,
respectively. The neighborhood connection weight (a) was varied to determine the
effect on performance. For all trials, the network converged to a solution that had k
units at maximum activation, and the remaining at minimum activation. However,
69


Count
a=0.0
101
8-
6-
4-
2
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
a=-0.4
Count lO-i f
8-
6-
4-
2-
trial converged to a
solution with a score
< 90% of the optimal
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
a0.8
Count 10-
8-
6-
4-
2-
1
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
Figure 4-3 K-Contiguous Winner Network Simulation Results (n=10,
k=3, a varied)
The distribution of the scores of the solutions found by the k-contiguous network
as a percentage of the score of the optimal solution. For each trial, the initial
activations were set to random values between 0.25 and 0.75. 'NF' indicates that
the network did not converge to a feasible solution.
70


Count
a=0.0
10n
8-
6-
4-
2
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
Count 10 -
8-
6-
4-
2-
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
a=-0.4
Count 10 -i
8-
NF 90 91 92 93 94 95 96 97 98 99 100
% Of Optimal
Figure 4-4 K-Contiguous Winner Network Simulation Results (n=10,
k=5, a varied)
The distribution of the scores of the solutions found by the k-contiguous network
as a percentage of the score of the optimal solution. For each trial, the initial
activations were set to random values between 0.25 and 0.75. 'NF indicates that
the network did not converge to a feasible solution.
71


when a=-0.8, the network occasionally converged to a solution where the winning
units were not contiguous. This may be due to the observation that as a approaches
-1, the network becomes a k-winner network and will no longer cluster the winning
units.
The score of the feasible solutions ranged from 89% to 100% of the optimal
score. Optimal solutions were found in 50% to 70% of the trials. Although it appears
that a=-0.4 yields the best results (most number of optimal solutions), not enough
trials were made to prove this conclusion statistically. These results of the simulations
are consistent with those of Shaw (1991).
Summary
Mapping the task duration problem to the k-contiguous network is readily
apparent. Each unit in the network represents a time interval, the arrangement of the
units represents a time line, and k represents the task duration. A unit at maximum
activation symbolizes a scheduled task; i.e., the task is to be performed during the
time interval represented by that unit. The initial activation of the unit represents the
preference associated with the time interval. Higher preferences, hence a greater
initial activation, indicate a greater desirability to perform the task during that time
interval.
The k-contiguous network has two major drawbacks. First, k must be odd.
The result of this limitation is that task durations must be an odd integer multiple of
the time interval. Secondly, the network is not linear, but rather circular. That is, the
72


network does not have ends that can be defined as the beginning and end of the time
line. The result is that a task may be scheduled over the desired end units, splitting
the task into two segments.
The first limitation may be solved by creating an asymmetric neighborhood.
The new neighborhood requires that the stability analysis performed earlier in this
chapter be repeated using the four units at both ends of the cluster.
The solution to the latter problem is to insert dummy units into the network
between the desired beginning and end units. By fixing the activation of these units to
the minimum activation bound, the network cannot converge to a feasible solution
that spans the end units.
73


CHAPTER 5 SCHEDULING PROBLEM
This chapter investigates a neural network solution to the task scheduling
problem that uses the networks described in previous chapters as building blocks. The
strategy of using simple networks as building blocks offers a powerful and natural
tool for designing networks to solve complex problems. This is somewhat
contradictory to mainstream thought that parallel algorithms requires that the problem
is approached in toto.
Unfortunately, the scope of the scheduling problem described in Chapter 1
had to be reduced to considering cost and duration constraints only; time did not
permit the addition of resource constraints.
Problem Formulation
The scheduling problem that will be considered in this chapter is formulated
find: xu
maximize: n m £ X piXft f=l /=1
maximize: n m ^ itXu t=l /=1
subject to: T-z< E ax,! < T t= 1
subject to: m 2 xit = di t= i
subject to: m-1 E XuXu+i di-1


where: xu=\ if task i is scheduled for time t, 0
otherwise
p{ is the priority of task i normalized by the
task duration
qit is the preference of performing task i at
time interval t
T is the target value of the total cost that can
be spent during each time period
e is the allowable bound about T
c,is the cost associated with task i
dps the duration of task i
n is the number of tasks
m is the number of time intervals in the time
span
Recall from the previous chapters that neural networks maximize a single
objective function. That is, the network tries to maximize the sum of the initial
activations of the winning units (units at maximum activation). The initial activation
is easily used to represent priorities or time interval preferences, but cannot
independently represent two different measures of performance. This limitation of the
scheduling problem formulation is overcome by encoding priorities within the time
interval preference to form a score. Scores may be simply generated by:
75


Sit -Pi + <]it
where: su is the score assigned to task i at time
interval t
qit is normalized over the time span so that
time intervals of greatest preference have
4,rl
Therefore, higher priority tasks will have greater scores than those of lower priority
tasks. The resulting objective function for the scheduling problem is:
n m
maximize: X X suxu
pi pi
Scheduling Network
The scheduling network can be thought of as a matrix of units (the matrix
need not be square). The rows of units represent tasks; the columns represent time
intervals. A unit at maximum activation in the i* row and /** column indicates that
task i is scheduled for time interval j. Operationally, the rows of the network try to
satisfy the duration constraints as the columns try to satisfy the cost constraints of the
scheduling problem.
A simple plan to design the network is to configure each row as a
k-contiguous winner network, and the columns as knapsack networks (Figure 5 1).
The knapsack networks are identical; i.e., the cost associated with each task and the
target value of the problem are the same for all columns. However, the k-contiguous
76


Figure 5-1 Scheduling Network
The scheduling network consists of n rows ofk-contiguous winner networks and m
columns of knapsack networks. The connection weights between units in a row are
as defined by the k-contiguous network; the weights between units in a column are
as defined by the knapsack network. The bias and self connection weights are the
sum of those definedfor each network type.
networks may differ in that d, the task duration, may vary from row to row (task to
task).
The connection weights across the rows of the network are defined by the
k-contiguous winner network. Similarly, the connection weights between units in a
77


column are defined by the knapsack network. Because each unit is connected in both
a k-contiguous winner network and a knapsack network, the bias and self connection
weights are the sum of those required by each network type. The resulting network
connections are:
Wm = a, mod^[/- k\, n j < J k
Wijtik = -l,mod(y-k\,n^>^Y^J*k
Wijjcj = ^<(x A.p jc.-c*, i*k
Wnji Xa ~ )c]
Wul = Q,i*k and j*l
bij = ^-(l-a) + ^- + XpTci,
where the saddlepoint of the knapsack
network is located at sc
b,j = -^-(1 a)+^i+- xp)rc, ^
/
where the saddlepoint of the knapsack
network is at sa
where: Wijkt is the connection weight from the unit
located in row k and column / to the unit at
row i and column j
by is the bias for unit located on row i and
column j
78


Essentially, the weight and bias matrices of the scheduling network are the sum of the
weights and bias matrices of n rows of k-contiguous winner networks and m columns
of knapsack networks. Both weight matrices are sparse, therefore, it is suspected that
the sum of the matrices will maintain the underlying dynamics of each network type.
Simulation Results
Figure 5-2 through Figure 5-7 exhibit the simulation results of the
scheduling problem with various problem and network parameters. Similar to
previous network simulations, these simulations were performed on a personal
computer using the program listed in Appendix A. The limited number of trials and
the small scale of the problems are indicative of the limitations of the hardware used
for simulation. A hardware implementation of the network, where each unit is a
single processor, would perform many orders of magnitude faster.
For the first four sets of trials, the complexity of the scheduling problem was
increased while holding the network parameters constant. The first set of trials
(Figure 5-2) involved a simple scheduling problem where the costs and durations of
each task were equal. The next set of trials (Figure 5-3) increased the complexity of
the problem by varying the duration of the tasks. Similarly, the third set (Figure 5-4)
used equal task durations, but assigned varying costs to the tasks. Finally, the fourth
set (Figure 5-5) used both varying durations and costs. The last two sets (Figure 5 -
6 and Figure 5-7) were similar to the previous problem, but varied problem and
network parameters. In all trials, solutions that satisfied cost and duration constraints
79


Target 3 3 3
0 Count 10 8-
r
LEGEND; 6 -
NC: Did not converge
FD: Converged to a non-feasible solution - 4 -
the contiguous time interval constraint
violated
TD: Converged to a non-feasible solution - 2-
3 3
cost and/or duration constraints violated
95-100: Converged to feasible solution -
number is percentage of final score to die
optimal score
NC FD TD 95 96
Knapsack Network
Parameters
V-s-o
Saddlepoint at sc
K-Contiguous
Parameters
a = -0.4
..I
97 98 99 100
% Of Optimal
Figure 5-2 Scheduling Network Simulation Results Equal Costs And
Equal Durations
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
80


Count 5 -
4-
LEGEND;
NC: Did not converge
FD: Converged to a non-feasible solution -
the contiguous time interval constraint
violated
TD: Converged to a non-feasible solution -
cost and/or duration constraints violated
95-100: Converged to feasible solution -
number is percentage of final score to the
optimal score
3-
2-
1 -
NC
I
FD TD 95
I
96 97 98 99 100
% Of Optimal
Figure 5-3 Scheduling Network Simulation Results Equal Costs And
Various Durations
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
81


Target 3 1 3 1 3
0 Count 5 4-

LEGEND? 3
NC: Did not converge
FD: Converged to a non-feasible solution the contiguous time interval constraint 2-
violated
TD: Converged to a non-feasible solution cost and/or duration constraints violated 95-100: Converged to feasible solution number is percentage of final score to the 1 -
optimal score J
3 | 3
I I
NC FD TD 95
Knapsack Network
Parameters
Saddlepoint at sc
K-Contiguous
Parameters
a = -0.4
96 97 98 99 100
% Of Optimal
Figure 5-4 Scheduling Network Simulation Results Various Costs And
Equal Durations
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
82


Knapsack Network
Parameters
\ 1-0
^=-S-0
Saddlepoint at sc
K-Contiguous
Parameters
a = -0.4
Count 5 -i
r
LEGEND:
NC: Did not converge
FD: Converged to a non-feasible solution -
die contiguous time interval constraint
violated
TD: Converged to a non-feasible solution -
cost and/or duration constraints violated
95-100: Converged to feasible solution -
number is percentage of final score to the
optimal score
NC FD TD
95
96 97 98 99 100
% Of Optimal
Figure 5-5 Scheduling Network Simulation Results Various Costs And
Various Durations (I)
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
83


Knapsack Network
Parameters
^=1-0
^=-50.0
Saddlepoint at sc
K-Contiguous
Parameters
a = -0.2
Count 5 -
4-
/ :-------------------------------------\
LEGEND:
NC: Did not converge
FD: Converged to a non-feasible solution -
tiie contiguous time interval constraint
violated
TD: Converged to a non-feasible solution -
cost and/or duration constraints violated
95-100: Converged to feasible solution -
number is percentage of final score to the
optimal score
v_______________________________________/
J
FD TD
95
96
97 98 99 100
% Of Optimal
Figure 5-6 Scheduling Network Simulation Results Various Costs And
Various Durations (II)
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
84


Target | 3 | 3 | 3 | 3 | 3 |
LEGEND:
NC: Did not converge
FD: Converged to a non-feasible solution -
the contiguous time interval constraint
violated
TD: Converged to a non-feasible solution
cost and/or duration constraints violated
95-100: Converged to feasible solution -
number is percentage of final score to the
optimal score
NC FD TD 95 96
97 98 99 100
% Of Optimal
Figure 5-7 Scheduling Network Simulation Results Various Costs And
Various Durations (ID)
Problem formulation, network configuration and distribution of the quality of
solutions found by the scheduling network. Diagram A illustrates the problem to
be solved. The matrix of circles represents the network and shows an example of a
feasible solution (the darkened circles represent units at maximum activation).
Diagram B lists the knapsack and k-contiguous winner network parameters used
during each trial. Lastly, diagram C shows the distribution of the quality of the
solutions found by the network. For all trials, the units were randomly initialized
to values between 0.25 and 0.75.
85


exactly (i.e., the allowable bound about the target value was 0) were considered
feasible. Any solution that violated these constraints was classified as non-feasible.
The units were initialized to random values between 0.25 and 0.75 to simulate
scores assigned to a task at a particular time interval. The network was allowed to run
until a solution was found or 2500 iterations, whichever came first. A solution was
found if all units were within 5% of the minimum and maximum activation bound.
That is, for all i, if a/0) < 0.05 and a,(0) > 0.95, then the network converged to
a solution.
For each trial, the result of the network was classified into one of three
categories: did not converge (denoted as NC in the Figures), non-feasible solution
found, and feasible solution found. Trials that fell into the second category were
further classified based on the constraint(s) violated if the time intervals were not
contiguous (denoted as FD in the Figures), or if the total cost and total time were not
equal to the target value or task duration, respectively (denoted as TD in the Figures).
Trials that fell into the last category, feasible solution found, were further
evaluated by comparing the total score of the solution found with that of the optimal
solution. The total score is defined as:
Score = X X arc(0)arc( 0) where ar,(0) = 0 or 1
The optimal solution was found using a simple depth-first algorithm. This algorithm
proved to be another limitation to the size of network that could be reasonably
simulated and evaluated. A network with 100 units would generally converge to a
86


solution in less than 30 minutes; the depth-first algorithm would find the optimal
solution in approximately 30 days.
As can be readily seen from Figure 5-2 through Figure 5-5, the
performance of the network degrades as the problem complexity increases. For the
most complex case (Figure 5 5), the network converged to non-feasible solutions
that violated the total cost and duration constraints. Interestingly, in two of the four
non-feasible solutions found, a single unit at maximum activation caused this
violation (Figure 5 8). If this unit were at minimum activation, the resulting solution
would be feasible and optimal. The remaining two non-feasible solutions exceeded
both the target cost of one time interval and the desired duration of one task. In both
cases, the contiguous time interval constraints were not violated (Figure 5 9).
To try to prevent violations of the total cost and duration constraints, the
simulations of the problem in Figure 5-5 were repeated (Figure 5-6) using different
network parameters (A,p decreased from -5 to -50, a increased from -0.4 to -0.2). Two
changes became evident in the network behavior: First, the network did not converge
to a solution more often. Secondly, for those trials that a solution was found, the
solution violated only the duration constraints; the total cost and contiguous time
interval constraints were not violated (Figure 5 -10).
Surprisingly, the two trials that converged to non-feasible solutions did not
schedule the task that was assigned a cost equal to the target value. This motivated
the creation of a problem where the costs assigned to tasks were less than the target
(Figure 5 7). Performance improved in that the network was able to find feasible
solutions in two of the five trials.
87


Duration
Total Cost 3 3 3 3 4
Target 3 3 3 3 3
Figure 5-8 Example Of A Non-Feasible Solution (I)
An example of a non-feasible solution found in the simulations of the problem
illustrated in Figure 5 5. If the unit marked with an X' was at minimum
activation, then the solution would be feasible and optimal.
Summary
At first glance, the performance of the scheduling network is disappointing.
But it is important to note that, although the network did not always converge to a
feasible solution, the results show that the network solves both the knapsack and
k-contiguous winner problems simultaneously. If this were not true, solutions would
have looked less like a schedule with more contiguous time interval, total cost, and
duration constraint violations.
88


Duration
Total Cost 3 3 3 4 3
Target 3 3 3 3 3
Figure 5-9 Example Of A Non-Feasible Solution (II)
An example of a non-feasible solution found in the simulations of the problem
illustrated in Figure 5 5. In this case, the total cost exceeds the target for one
time interval, and the total duration exceeds the desired for single task. The
contiguous time interval constraint is not violated, however.
Many of the non-feasible solutions found by the network are reasonable,
although not efficient, schedules. Most of these solutions exceed the target value by
the minimum cost, and extend the task duration by a single time interval. Certainly if
a minor increase in total cost can be tolerated (i.e., the allowable bound about the
target value is greater than 0), then these solutions are usable.
Several factors contribute to the performance of the network. Obvious factors
gleaned from the simulations discussed in this chapter are the complexity of the
problem to be solved and the network parameters. Another factor is the size of the
network. As the size of the network increases, the number of feasible solutions also
89


Duration
Total Cost 3 3 3 3 3
Target 3 3 3 3 3
Figure 5-10 Example Of A Non-Feasible Solution (IQ)
An example of a non-feasible solution found in the simulations of the problem
illustrated in Figure 5-6. The total cost constraint was satisfied for all time
intervals, but the total duration constraint was violated for 3 tasks. Again, the
contiguous time interval constraint was not violated.
increases. This raises the likelihood that the network will converge to a solution and
that the solution is feasible. Additionally, a potential factor is the initial state of the
network (the initial activations of the units). The initial state determines which
solution the network will find. Rather than using random values, scores that combine
time interval preference and task priority would initialize the network to a state that
looks like a schedule. Perhaps this will reduce the frequency of the network not
converging to a solution, and increase the likelihood that the solutions found are
feasible. All of these factors warrant further investigation before a reliable scheduling
network can be realized.
90