Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00003499/00001
## Material Information- Title:
- Solving the task scheduling problem using neural networks
- Creator:
- MacMillan, James M
- Publication Date:
- 1992
- 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 )
## Auraria Membership |

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 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 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- \ 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 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 |