Vishnu User's Guide

I. Introduction

I.1 What is Vishnu?

So, if you have a scheduling problem that you've been trying to solve better, Vishnu may be the solution for you.  You can tailor the type of data that will be optimized and specify in detail how that data should be used in forming a meaningful schedule, what dependencies that may exist between elements of the schedule, and how to determine the goodness of a given schedule.  You can also tailor the details of the search algorithm to allow for a detailed, fine-grained search if the best possible schedule is needed irregardless of real-time, or to allow for a quick and dirty search that will find the best solution it can as quickly as possible.  It is all in your hands - you provide both the problem-specific data and the problem-specific logic to guide the search.  Vishnu provides the framework you need to enter that knowledge and a proven back-engine that will chug away for you.
 

I.2 Vishnu Technology

I.3 What is a Scheduling Problem  in Vishnu?

Given a set of tasks and resources, there are a variety of possible schedules since tasks may be assigned to different resources in different orders at different times.  In the most general case, Vishnu will assume that all tasks are fully independent and that they may be assigned to any resource in any order at any time, so long as they are given a sufficient time interval on the resource that they are finally assigned to.  This is very simplistic, and in most interesting problems there are a variety of dependencies that may exist among the tasks and between the tasks and resources.   For example, a task may require that certain other particular tasks, regardless of which resources they are assigned to, be complete before it can start.  This notion of a pre-requisite is one of several dependencies among tasks supported by Vishnu.  As another example, a task may require that it be assigned to a subset of the resources since it is not capable of being performed on certain resources.  This notion of capability is one of several dependencies between tasks and resources supported by Vishnu.  Problems may also have constraints placed upon the tasks and resources.  For example, a particular resource (e.g., a computer) may not be available at all times due to known issues (e.g., goes down for backup every day from 1:00 am to 2:00 am).  This notion of unavailability is one of several constraints supported by Vishnu.

Defining a scheduling problem in Vishnu requires a complete specification of all tasks, all resources, all dependencies among tasks and between tasks and resources, and all constraints on tasks and resources.  Together, these define what constitutes a valid schedule.  Finally, defining a scheduling problem in Vishnu also requires an explicit specification of a function that measures of how good a particular, valid schedule is.  Without this optimization criterion, Vishnu is unable to compare schedules and search for the best possible one.

 The idea is simple: Let Vishnu know what defines a legal schedule, and how to compare different schedules, and Vishnu will search for the best schedule it can find.
 

I.4 What Kinds of Problems can be Solved by Vishnu?

The remainder of this tutorial will describe the details of defining, creating, and executing a scheduling problem in Vishnu.  The above two problems will be revisited occasionally to illustrate the finer specification details.
 

II. Defining a Vishnu Scheduling Problem

II.1   Overview: How is a Problem Specified in Vishnu?

Now that we have a basic understanding of what a Vishnu scheduling problem involves, it will be helpful to more concretely detail the specifics of a Vishnu problem (and how they are manipulated using the Vishnu on-screen interface).

Recall that the basic Vishnu problem is solved by legitimately and optimally assigning tasks to resources.  In Vishnu, we specify only one task type and one resource type per problem.  This is analogous to specifying a user-defined data type in a high-level programming language like C.  Once a task type (resource type) has been defined, we may create task instances (resource instances) that store the data corresponding to the tasks (resources) of the problem. When defining a task type or resource type, we specify for each a number of data fields.  Each field may be given an arbitrary name and the information stored in the fields is given one of several formats (e.g., string, list and number), as will be detailed later.   The task type (resource type) must contain a minimum of one field, and must have a field which stores a unique value that is used to distinguish task instances (resource instances) from each other.  This field is known as the KEY field.

For example, in the traveling salesperson problem we attempt to find the optimal path for a salesperson (a resource) to take through a number of cities (each city being a task that needs to be accomplished).  Note that in this problem there is only one type of task, a City, but that there are multiple instances of that task.  When defining the task type for this problem, as a bare minimum we would want to include a field such as name to store the name of the city as a string and a field such as distances to store the distances from all the other cities to the current one as a list.   Information in a list is indexed much in the same way as an array.  So, our task type would also require a field such as index to store a unique index number for that city to correspond to the entries in the distances lists of other cities.  We make the index field the KEY field of the task type since it contains unique values.  Following our design of the TSP problem in the previous section, we would also include a field such as preceding_cities in the task type.  The value of preceding_cities would store as a list all the cities that the salesperson must visit before the current one.

But, we now arrive at a fundamental design issue in Vishnu.  The information present in the fields of the tasks and resources is simply that: information.  We may add any arbitrary number of fields with arbitrary names to a given task type or resource type and store a variety of actual data in the corresponding fields of the task and resource instances, but this does not explain to Vishnu how to treat such information.  The user needs to define logic rules that use the data in the various fields to define the dependencies, constraints and optimization criteria that constitute a complete scheduling problem in Vishnu.  In particular, Vishnu allows the user to define 17 different logic rules using a Vishnu-specific functional language (detailed later).  Each logic rule represents a function that is used by the optimization system in a fixed manner.  Each logic rule has a default function, which the user may override with a new user-defined function.  For example, Vishnu contains a logic rule called Prerequisites which, when executed for a given task, returns a list containing the KEY value of all other tasks that must occur before that task.  By default, it returns the empty list.  In our TSP example, we have made the specification of that rule easy since it merely has to perform a lookup on the task's preceding_cities field.  The syntax of this specification is described later.
 
 

Travelling Salesperson Problem: City (task type) Salesperson (resource type) Field Name  Field Type  name string index  (KEY) number distances list preceding_cities list Field Name Field Type  name (KEY) string Sample Cities: Consider TSP with 3 cities: Washington, D.C.; Boston, MA; and New York, NY.  If our salesperson lives in Washington, we would want that to be our starting and final city.  Based upon the design above and in the earlier section, we would create the following task instances to define our problem.     Washington_first (task instance) Boston (task instance) New York (task instance) Washington_last (task instance) Field Name Field Value name Washington D.C. index 1 distances 0, 440, 225, 0  preceding_cities Field Name Field Value name Boston index 2 distances 440, 0, 217, 440  preceding_cities 1 Field Name Field Value name New York index 3 distances 225, 217, 0, 225  preceding_cities 1 Field Name Field Value name Washington D.C. index 4 distances 0, 440, 225, 0  preceding_cities 1, 2, 3 Logic Rules (incomplete):    Prerequisites: task.preceding_cities

In some problems, it is necessary or convenient to store information in variables that are not directly associated with the tasks or resources.  These may be thought of as "global" variables.  Vishnu includes the capability of defining an arbitrary number of global types and creating an arbitrary number of instances of each.  A field of a task type, resource type or other global type may be a reference to a global instance or may be a instance of the global type itself.  As a fun example, we could create a global type called TV_show which stores the name, producer, network, and actors of a given television show.  We could create several global instances of TV_show (e.g., Friends, Star Trek, Ally McBeal).  At the global level, we now have data that may be referenced by our cities.  We could add a field called most_watched_show to the task type, and then enter a specific show in each city (task instance).  Two or more cities could share the same show.  Of course, this information has no bearing on the TSP problem, but it illustrates how global instances may be referenced.
 
 

In the following sections, we will describe what is involved in each of these steps.  As we go, we will describe both the design issues involved as well as the practical steps that are required in manipulating the user interface.
 

II.2 Vishnu Data Types

II.2.1 Predefined Types

• predefined atomic types:
• string - A string is any combination of standard characters.  It may not contain the following five characters:  " < > & ,
• number - A number can be an integer or a floating point number.
• boolean - A boolean has value either "true" or "false".
• datetime - A datetime is formatted as "YYYY-MM-DD HH:MM:SS".
• list - A list is a set of values of another type of unspecified length. All the elements in a particular list should be of the same type.  The data type of the elements can be any predefined type other than a list or it may be a user-defined type. If you need a list of lists, either use a matrix (see below) or define an object type to contain the inner lists.
• predefined object types:
• interval - An interval represents an interval of time and contains the fields:
• start - A datetime specifying the start time of the interval
• end - A datetime specifying the end time of the interval
• label1 - A string that can be null (but is usually used for resource unavailabilities, as discussed below)
• label2 - A string that can be null
• xy_coord - An xy_coord represents a point in x-y coordinates and contains the fields:
• x - A number specifying the x coordinate
• y - A number specifying the y coordinate
• latlong - A latlong represents a point on the earth's surface and contains the fields:
• latitude - A number between -90 and 90 specifying the latitude
• longitude - A number between -180 and 180 specifying the longitude
• matrix - A matrix is a two-dimensional array of numbers and contains the fields:
• numrows - A number specifying the number of rows
• numcols - A number specifying the number of columns
• values - A list of numbers of length numrows * numcols to fill in the array by rows

II.2.2 User-Defined Types

1. All user-defined types must have unique names.
2. Any name may be given to a user-defined type, so long as:
• it starts with an alphabetic character
• all characters in the name are either alphabetic, numeric, or '_'
• Note, specifically, that type names may not have spaces in them
3. A task (resource) type must contain a minimum of 1 data field, which will contain aKEY value that will uniquely identify all task (resource) instances.
• The name of the KEY field may differ from the name of the task (resource) type itself.
• The type of the KEY field is always a string.
4. A global type does not contain a KEY field.  Instead, the name of each instance is used to uniquely identify that instance.  A global type may thus have 0 or more fields.
5. Fields in a user-defined type (including the KEY field) may be given any name, so long as:
• it is different from all other field names in that user-defined type
• it starts with an alphabetic character
• all characters in the name are either alphabetic, numeric, or '_'
• Note, specifically, that field names may not have spaces in them
6. Each field is assigned a specific data type.  When assigning a type to a field, the following options are available:
• a predefined atomic type (string, number, datetime, boolean)
• a pointer to an instance of a predefined object type (interval, latlong, xy_coord, matrix)
• an encapsulated predefined object type
• a pointer to an instance of a global type
• an encapsulated global type
• a list containing elements of a specific predefined type or global type.

An encapsulated global type allows a data field to become a complex data field with multiple sub-fields.  We can thus distinguish between "top-level" fields of an object and "lower-level" fields.  Note that neither a task type nor a resource type may be assigned to a field in any user-defined type (i.e., not in a global type, task type, nor resource type).  Also note that within user-defined global types, circular encapsulations are possible in the current implementation, but will eventually cause an error.  So, the user must be careful to avoid these.  (In later versions, circular dependencies will be avoided automatically.)
 

II.2.3 User-Defined Instances

1. All task instances must have a unique KEY value.
2. All resource instances must have a unique KEY value.
• These are permitted to be the same as the KEY values of task instances.
3. Global instances may be instances of a predefined object type or of a user-defined global type.
4. All global instances, regardless of type, must have unique names.
•  For example, if there are five instances of global type A, three instances of global type B, and two instances of latlong, then all ten instances must have different names.
• These names are permitted to be the same as the KEY values of task or resource instances.
5. The name of any task, resource or global instance may be any arbitrary string
• e.g., spaces, punctutation, etc are permitted.
• Note the difference: the name of the type has a strict format, but the name of an instance is just a string
6. If a user-defined object contains a field that is a global pointer, then the user should fill in the name of a global instance of the appropriate type.
• Note that Vishnu does not currently verify this information for you, so please ensure that the instance is created and of the appropriate type.  (Later versions will perform automatic verification).
7. If a user-defined object contains a field that is an encapsulated type, then the user will be prompted to enter the appropriate information for the lower-level fields.
• Lower-level fields are indicated through the use of an accessor.   Say a field in the object type "City" is named "statistics" and has an encapsulated global type of "City_Stats".  Say "City_Stats" has three fields: "founding_date", "location" and "population".   When creating an instance of "City", you would be prompted to enter a value for "statistics.founding_date", "statistics.location" and "statistics.population".  When the fields within the encapsulated object are themselves encapsulated objects, those lower-levels will be indicated through a chain of accessors.  This syntax should look very familiar to programmers of object-oriented languages.

II.2.4 Keyword Variables

Keyword variables available to all logic rules:

• tasks - a list of all task instances
• resources - a list of all resource instances
• start_time - the start of the scheduling window as a datetime object
• end_time - the end of the scheduling window as a datetime object

Keyword variables available to only certain logic rules.  The descriptions may be slightly cryptic at this point, but will be elaborated upon later.

• task - the task instance that is currently being considered for insertion into the schedule
• resource - the resource instance that is currently being analysed
• prerequisites - a list of all task instances that have been computed to be the prerequisites of task
• previous - the task instance that occurs before task, assuming a tentative insertion
• next - the task instances that occurs immediately after task, assuming a tentative insertion
• duration - the task duration (for certain rules, this is available since it is computed by the underlying interpreter before the rule is executed)
• assigned_so_far - all resources to which a task has been assigned so far (primarily for multitasking)
• task1,task2 - used by Groupable rule to refer to two generic tasks (i.e., to compare them to see if they can be in the same group)

II.3 Vishnu Specification Language

II.3.1 Basic Functions

The basic functions in the Vishnu specification language are described in the table below.   Each function has a unique name (e.g., 'mod') as indicated in column 1.  The function accepts specific parameter types (e.g., 2 parameters: a 'number 'and a 'number'), and returns a specific type (e.g., a 'number').   This is indicated in the second column (e.g., '(number, number) => number' ).  In the specifying the parameter and return types, 'type' refers to an arbitrary data type (predefined or user-defined) and '?' refers to an arbitary extra number of like elements.  A verbal description of each function is provided in the third column.  For ease of interpretation, the functions in the table have been grouped roughly according to their main purpose.  Most functions are fairly straightforward.  The iteration functions require a bit more careful attention in order to understand exactly what they are computing.
 
 

II.3.2 Task Functions

Task functions are used primarily to extract assignation data that is associated with a task instance.  In addition to the user-defined fields of a task type, each task instance contains several "hidden" fields that may be accessed only through these functions.  These hidden fields contain information about how that task has been assigned to a resource by the underlying Vishnu scheduler.

Note an obvious conclusion: in order to use these functions to access a task, that task must have already been scheduled.  These functions are typically used in one of two ways when defining logic rules:  (1) Given a certain interim state of the schedule, we can use information about the tasks already scheduled to add a new task to the schedule; (2) Given a complete (or partial) schedule, we may use the information about how the tasks were scheduled to evaluate how good that (partial) schedule is.
 
 

II.3.3 Resource Functions

Similar to task functions, resource functions are used primarily to extract assignation data that is associated with a resource instance.  Most of these functions perform a computation based upon how tasks are currently scheduled on that particular resource.  These functions are typically used when evaluating how good a complete or partial schedule is.
 
 

II.3.2b Misc Functions

II.3.4 Operators

Arithmetic operators are (+, -, *, /), which add / subtract / multiply / divide two numbers.

• addition (+) can also add a datetime and a number (of seconds) to get a new datetime
• subtraction  (-) can take the difference of two datetimes to get a number (of seconds) or the difference of a datetime and a number to get a datetime. For example, taskstarttime(task) - start_time will give the number of seconds after the start of the scheduling window that task has been scheduled.

• In the case of <, <=, >, and >=, the two values must be either two numbers or two datetimes. For example, resource.location.x < 10 will return true if the value of the referenced field is less than 10 and false otherwise.

II.4 Vishnu Constraints and Logic Rules

II.4.1 Expressions

• Constants - There are three types of constants: numeric, string, and boolean. An example of each of these are 21.3, "hello world", and true. Note that all string constants are quoted to distinguish them from variables.
• Variables - There are three ways that variables are defined.
• First, there are some variables that are predefined. These always include tasks (a list of all tasks), resources (a list of all resources), start_time (the start of the scheduling window), and end_time (the end of the scheduling window or, if that is not set, the "end of time"). Additionally, there can be predefined variables specific to each constraint. In the tables below that describes the constraints, we list the associated predefined variables for each constraint.
• A second way to define variables is using global data. The name associated with a global instance is the variable name that references that instance.  Note that it is therefore important to ensure that the variable names do not conflict with the keyword variables. (Current implementation permits such naming conflicts, but future versions will not allow them)
• A third way to defined variables is using iteration functions such as loop, mapover, sumover, and maxover. These functions take as an argument a string which becomes the variable name that allows access to the iterated value (e.g., the current list entry for this iteration).  Again, it is important to avoid naming conflicts with keyword variables.  (Future versions will not permit this)
• Accessors - Accessors provide the means to access the fields of an object. To access a top-level field, use a '.' followed by the field name. For example, task.id will access the id field of the variable task. When the fields within an object are themselves objects, chaining together accessors will access lower-level fields. For example, resource.location.x will access the x field of the location field of the variable resource. Global pointers act just like other fields in terms of chaining of accessors.
• Operators - There is a set of arithmetic operators (+, -, *, /) that add / subtract / multiply / divide two numbers. Addition can also add a datetime and a number (of seconds) to get a new datetime, while subtraction can take the difference of two datetimes to get a number (of seconds) or the difference of a datetime and a number to get a datetime. For example, taskstarttime(task) - start_time will give the number of seconds after the start of the scheduling window that task has been scheduled.
• There is another set of comparison operators (=, !=, <, <=, >, >=) that compare two values of the same type and return a boolean. In the case of <, <=, >, and >=, the two values must be either two numbers or two datetimes. For example, resource.location.x < 10 will return true if the value of the referenced field is less than 10 and false otherwise.
• Functions - There is a (growing) set of functions that can be used in expressions. A function has the form fcn_name (arg1, ..., argn). The arguments to a function are themselves expressions that are evaluated as part of the process of evaluating the function. An example of an expression involving functions is if (task.use_resource, resourcefor (task), resource).  Some sample expressions are:
• abs (task.location.x) * (mod (task.location.y, 5) + 2)
• if (resource.name = "machine 1", "the one", resource.name)
• mapover (tasks, "task1", task1.prerequisites)

II.4.2 Genetic Algorithm

The genetic algorithm component uses an order-based chromosome. Each chromosome is a list of all the tasks that need to be scheduled in a particular order.  The initial population generator creates random orderings of the tasks. The mutation operator picks some of the elements of the parent's list (that in general are not contiguous) and shuffles their order to create the child. The crossover operator picks some of the elements of the first parent's list and puts them in the order they are in the second parent.   To evaluate each chromosome, it is passed to a decoder that uses the greedy scheduler to translate each ordering of tasks into a schedule.  Finally, the fitness of the schedule is evaluated and it is inserted into the population accordingly.  (Note that the fact that the decoder itself does a simple optimization means that the genetic algorithm does not have to work as hard. Even if the genetic algorithm generates just a single individual, this individual will generally always be a much-better-than-average schedule and can potentially even be optimal if there is little or no contention for resources. This is important to keep in mind when choosing genetic algorithm parameters.)
 
 

The key constraint upon the genetic algorithm is that only certain orderings of the task are valid.  The validity of a given task ordering is determined by the logic rule Prerequisites.  For each possible task instance, this rule specifies a list of all other task instances (by name) that must occur before it.  By default, Prerequisites returns the empty set.  The population generator and all genetic operators will always obey the constraints given in this rule.  Note that it is possible to specify a circular constraint, in which case an error will occur when the initial population is created (since no valid ordering is possible).  Future versions may include some logical debugging that will avoid this in simple cases.

Once a chromosome has been passed to the greedy scheduler and decoded into a schedule, the fitness of that chromosome is determined by the logic rule Optimization Criterion.  For a given complete schedule, this rule returns a single number reflecting the fitness of that schedule.  By default, Optimization Criterion returns a constant of 0.  The chromosome is inserted into the population based upon this fitness value and the value of the constraint Optimization Direction.  This constraint is either "minimize" or "maximize" and is not an expression.  By default, the value is "minimize".

Table 1 lists the genetic algorithm constraints along with what data type the expression needs to return, what variables other than tasks, resources, start_time and end_time are defined in its context, what is the default value, and a short description of the purpose of the constraint.
 

II.4.3 Greedy Scheduler

1. Take the first element in the list that is not yet scheduled (or marked unscheduled) and for which all of the tasks in its lists of prerequisites are already scheduled.
2. For each resource eligible to performing this task, find the nearest possible available time interval of sufficient length and temporarily assign the task to that resource at that interval.
3. Evaluate how good each assignment is
4. Keep the assignment to that resource that is the best (i.e., perform a greedy selection of resource).

1. Resource Eligibility:
• A resource may be considered inelgible since it may not be capable of executing the task in question.
• The Capability logic rule determines whether a resource can perform a particular task.  In step 2, the scheduler computes this logic rule for the task in question to determine all the capable resources.
• A resource may also be considered ineligible since it may not have enough capacity to handle the task in question.
• A fixed number of resource supplies are considered to exist.
• The Capacity Threshold logic rule specifies the initial quantity (or capacity) of every supply that is available on a particular resource.  Each resource may have a different capacity for each supply.  For each new individual, each resource starts with the amount of each supply indicated by Capacity Threshold.
• The Capacity Contribution logic rule specifies how much of each supply a particular task will require.  This may be dependent upon the resource that the task is assigned to, and may be dependent upon a specific temporary assignment of that task.
• Every time a task is assigned to a schedule, the capacity of remaining supplies are reduced by the amounts consumed by that task.
• Together, these two logic rules ensure that the capacity thresholds are not exceeded over the history of the resource.
• By default, resources have no supplies and tasks require no supplies.
2. Nearest Time:
• The Best Time logic rule determines a "starting point" from which the scheduler tries to find a large enough time interval for performing a specific task.  By default, the overall start_time is used.  The scheduler will actually search in both directions from the best-time for the nearest sufficient interval.  To restrict the time search to only times after the best-time, explicit constraints must be provided through other logic rules below.
3. Available Time:
• The Task Unavailability logic rule determines which periods of time to block off in terms of not allowing the given task to be scheduled during those times.  It returns a list of time intervals, which by default is empty.  This rule is called every time a task is chosen in step 1 of the greedy scheduler.  It is computed based upon the partially completed schedule so far.  Thus, the value for a particular task may potentially vary from chromosome to chromosome.
• Another way of viewing this logic rule is that it includes the "semantics" for the effect of the pre-requisites.  (Note, other unavailabilities may be included as well).  So, if we specify that Task A is a pre-requisite to Task B, then in Task Unavailability, we must indicate what timing constraint we mean to have imposed.  For example, we could enforce that Task A cannot start until Task B finishes.  Or, we may simply enforce that Task A may not start until after Task B has started.  We may force a rest period between the completion of B and the commencement of A, and so on.   Note: Vishnu doesn't help you out here.  It is up to you to include the correct semantics for the pre-requisites.
• (to verify with Dave)  If no task-unavailable-times constraints based upon pre-requisites are included, then the "pre-requisite" effectively becomes a priority on the placement of the tasks (first-come/ best-served).  i.e., Task B would tend to be placed nearer to the best-time than Task A would be.
• The Resource Unavailability logic rule determines when a given resource cannot be scheduled for a task.  It returns a list of time intervals, which by default is empty.  This rule is called exactly once - at the beginning of the genetic algorithm.  The constraints thus do not vary from chromosome to chromosome.
• Together, these two rules provide a specification of when a task may execute upon a resource.
4. Sufficiently Long Time Interval
• By default, every task has a duration that is independent of all other tasks and independent of the resource it is assigned to.  However, three logic rules allow the user to introduce certain dependencies.
• When the current task is being assigned to a resource, it is assumed to have a setup duration, a core duration, and a wrapup duration.
• The Core Duration logic rule determines how much time the current task takes.  This may be dependent upon the resource to which the task is temporarily assigned.  By default the core duration is 0.
• The Setup Duration logic rule determines how much time the task (A) must spend in setting up.  This may be dependent upon the resource as well as upon the task (B) that was scheduled before A.  The rule may use the keyword variable previous to access B.  By default, the setup duration is 0.
• The Wrapup Duration logic rule determines how much time the task (A) must spend in wrapping up.  This may be dependent upon the resource as well as upon the task (B) that was scheduled afterA.  The rule may use the keyword variable next to access B.  By default, the wrapup duration is 0.
• How the greedy scheduler decides an interval is sufficiently long for task A.
1. Starting at best-time, find the next non-zero, available interval after best-time.
2. For that interval, temporarily assign A to that interval.  Generally, A will be slotted in between two tasks previous and next.
3. Compute the effect of A upon the wrapup duration of previous and upon the setup duration of next.  Compute the setup and wrapup durations of A itself (given previous and next).
4. If A can still fit in between previous and next, we have found a valid interval.
5. If A does not fit, return to step a and continue until a valid interval is found
6. Repeat, searching for a valid interval before best-time.
7. Return the valid interval that is closest to best-time.
5. Goodness of Temporary Assignments
• The Delta Criterion logic rule is used by the greedy scheduler to evaluate the partial schedules that arise from assigning the task to each eligible resource.  The rule should return the effect that a particular assignation has upon the overall fitness of the schedule.  The best Delta Criterion of all assignations (lowest if Optimization Direction is "minimizing", highest if Optimization Direction is "maximizing") is selected as the greedy choice.  Ideally, the sum of all the delta criterions of all the greedy choices that were made should equal the result of the Optimization Criterion logic rule.

Other Logic Rules:

1. The Multitasking constraint determines how resources handle multiple tasks at once.

• A value of none implies that a resource handles only one task at a time.
• A value of grouped implies that a resource can handle multiple tasks at once only if they start and end at the same times.
• A value of ungrouped implies that a resource can handle multiple tasks without the need to coordinate the start and end times.
• A value of ignoring time implies that no time-based calculation will occur. This means the problem will be of the knapsack variety, like the Generalized Assignment Problem.
• The Capacity Contribution and Capacity Threshold constraints apply differently depending on whether or not there is multitasking.
• When there is multitasking, the capacity constraints ensure that none of the different types of capacities are exceeded at any given time.
• When there is no multitasking, these constraints ensure that the capacities are not exceeded over the history of the resource.
1. The Groupable constraint applies only for grouped multitasking and determines when two tasks can be performed by a single resource at the same time. Groupability is assumed to be defined to be both
• reflexive (if task1 is groupable with task2 then task2 is groupable with task1) and
• transitive (it task1 is groupable with task2 and task2 is groupable with task3, then task1 is groupable with task3); any non-transitive aspects of groupability can generally instead be handled using multiple capacities.
2. Linked/Link Time Difference

II.4.4 Logical Debugging

The second mechanism is handling of undefined values encountered during runtime execution. It is sometimes possible for a function to have no valid value to return. For example, taskstarttime has no valid value to return if the task that is its argument has not been assigned yet and therefore does not have a start time. In this case, the function returns the value null. All functions, operators and accessors are capable of handling a null value by passing along null as a result. If the user wants to explicitly handle a null condition, there is a function hasvalue that tests whether a particular value is null.
 

Appendix A: Vishnu Interface Tutorial

Appendix B: Vishnu Architecture and API

Vishnu has essentially a client-server architecture. The server consists of a relational database (MySQL) and a web server (Apache) with PHP modules that provide dynamic content for the serviced URLs. There are three types of clients: browsers for display and user interaction, automated schedulers for generating optimized schedules, and (optionally) application drivers that potentially provide the data and read back the generated schedules.

The database is capable of holding an arbitrary number of problems (within disk space limitations), with the provision that each problem must have a different name. There is one database instance for every problem, each named vishnu_prob_[probname]. The database for each problem contains all the data formats (see Section 3), data (see Section 3), scheduling specifications (see Section 4), automated scheduler specification (see Section 5) and the results from the automated scheduler (see Section 5).

There is one additional database instance called vishnu_central that serves as a central point. It contains a list of all the problems and a list of all requests for the automated scheduler to run.

All interactions of the clients with the database are via the web server. The client sends data to a URL, and the web server processes the request, making the appropriate database interactions and returns data to the client. For the URLs used by browser clients, the data returned is HTML data and other data (such as images) that the browser can display. For the URLs used by the automated schedulers and application clients, the data is in XML format. The data sent to the URLs is in the form of typical URL arguments. Any complex data is in XML format within the URL arguments.
 

There can potentially be more than one automated scheduler. They can either be on the same machine as the database or on a different machine because all communication is via URLs. Each automated scheduler queries the database at regular intervals to see if there are any new problems. When there is a new problem, the scheduler needs to query the database for the problem contents, solve the problem (i.e., create a new schedule), and then write the schedule to the database.

There are six different URLs that the scheduler needs to access. These are:

• currentrequest.php - This URL allows the scheduler to query whether there is a new problem to solve and what it is.
• ackrequest.php - This URL allows the scheduler to specify an integer between 0 and 100 (inclusive) telling how far along it is on solving the problem. The scheduler is required to change this to a value between 0 and 100 (exclusive) when it is starting to work on the problem and 100 when it has finished. Currently, the scheduler changes the status to 1 when it starts work and 100 when it is finished but does not provide intermediate values.
• data.php - This URL queries for the metadata and data for a particular problem.
• specs.php - This URL queries for the scheduling specifications.
• gaparms.php - This URL queries for the genetic algorithm parameters.
• postassignments.php - This URL allows the scheduler to write the schedule into the database.

Expression (or Formula) Compiler

There are two different URLs that the expression compiler needs to access:

• compilerrequest.php - This URL queries the database for any outstanding requests for expression compilation, and if one exists, returns the expression plus all the context data required to perform the compilation.
• postcompilerresult.php - This URL allows the expression compiler to write back the XML text or else an error message for what went wrong.

GUI/Browser Clients

The client side of the GUI is just a standard web browser. The server side of the GUI is PHP code that reads from the database and dynamically serves up HTML to the browser. Using the GUI, a user can load a problem or data for a problem from a file, request the scheduler to run, check the scheduler's status, and view the data from a problem and the associated schedule in a variety of forms.

We do not list all the URLs that the GUI uses, as these are too numerous and easily deduced from the PHP code. We leave until see Section 6 a more detailed explanation of what the GUI actually does.
 

Application Clients

The URLs used are:

• postproblem.php - This URL allows the client to create or modify a problem. The single argument is data, which should contain XML data of the format specified in Appendix B.
• postdata.php - This URL allows the client to add, modify, or delete object data for an existing problem. The two arguments are problem and data, where problem specifies the problem name and data contains XML data of the format specified in Appendix B.
• postkickoff.php - This URL allows the client to request the scheduler to run on the data for a problem. The two arguments are problem and username.
• readstatus.php - This URL allows the client to tell whether the scheduler is done generating the scheduler. The single argument is problem. The text sent back will have the form percent_complete=[value], where value will be 100 when the scheduler is finished.

assignments.php - This URL allows the client to read the assignments that the automated scheduler made. The single argument is problem. The text sent back will be XML assignment data in the format

The scheduler stops running when any of the following four quantities exceed their specified limit: (1) the elapsed time for the run, (2) the total number of individuals evaluated, (3) the number of consecutive evaluations without an improvement to the best individual, and (4) the number of duplicate individuals generated.

When the scheduler stops running, it writes the following information back to the database: (1) the set of all assignments of tasks to resources, including the times (setup start, task start, task end, and wrapup end) and the color and text to be displayed and (2) the set of non-task activities for each resource, including times, color and text. 

The following table provides the parameters that can be varied to control the genetic algorithm performance:

Appendix C: Cougaar-Vishnu Bridge

Cougaar is an architecture for construction of large-scale, distributed multiagent systems. Vishnu provides a way to easily integrate one or more Vishnu schedulers into a multiagent system based on Cougaar. This section uses Cougaar terminology and concepts extensively, so interested readers should first familiarize themselves with these first before attempting to read this section.

The Cougaar-Vishnu Bridge is used to connect a Cougaar plugin to the Vishnu Scheduling System. The bridge is instantiated in the usual plugin flavors: expander, allocator, and aggregator. Typically an allocator would be used for a one-to-one scheduling problem (multitasking = none/ignoring_time) and an aggregator for a many-to-one problem (multitasking = grouped/ungrouped). (Sometimes a task-to-resource assignment needs to be made in an expander and that assignment recorded in prepositions on the new subtask of the expansion. Such an assignment might be a piece of necessary information for a downstream plugin.)

The Bridge interfaces between a Cougaar plugin and Vishnu by mapping Cougaar tasks and assets to Vishnu tasks and resources. LDM objects are translated into Vishnu objects so they can be manipulated by the Vishnu scheduler. The scheduler creates Vishnu assignments, and these are used to create plan elements.

When a bridge plugin receives a task for the first time, it sends its problem definition to Vishnu. The problem definition is composed of the object format of the tasks and resources, the scheduling specs, the GA parameters, the object format of any other data that is neither task nor resource, and that other data itself.

The associated files are, by default, the name of the cluster, with a suffix identifying the type of file. For instance, a cluster named Sample with a bridge plugin might have the following files:

• Internal or Web Server
• Incremental or Batch
• XML or Direct Translation
• Automatic or Custom Translation

Internal or Web Server

In web-sever mode, each instance of a bridge plugin gets its own Vishnu problem name. Each instance of a bridge plugin maps to a problem in the Vishnu database that will appear on the problem list page on the web server.

Incremental or Batch mode

In incremental mode, Vishnu maintains incremental state, remembering previous assignments. This allows the scheduler to continue assigning tasks to nearly empty resources. The default mode for GLMTrans, for example, is incremental. In addition, the number of tasks in a batch is not as important in incremental mode, allowing smaller batches and in larger societies, better performance. The reason for this is if one agent depends on the results of another, it is better to have the dependent agent process many small batches quickly, instead of doing one large batch, returning one large set of results after a long wait.

Not all types of problems benefit from incremental mode. Grouping problems would tend to be better run in incremental mode.

XML or Direct Translation

• XML Translation

LDM objects are translated into XML of a form that Vishnu understands, and Vishnu assignments, expressed in XML are returned, and used to create plan elements.

• Direct Translation

In neither mode is the plugin developer required to decide whether XML or Direct translation is being done. This handling is at the dataHelper level of abstraction.

Automatic or Custom Translation

Custom mode has the advantage that only the fields that are necessary for the problem are defined and sent. This can greatly increase performance. The GLMTrans society runs in this mode. The disadvantage is that the plugin developer is forced to write translation code.

Custom Translation

Default file format

<?xml version='1.0'?>
<PROBLEM name="TRANSCOM" >
<DATAFORMAT>
<OBJECTFORMAT name="Transport" is_task="true" is_resource="false" >
<FIELDFORMAT name="id" datatype="string" is_subobject="false" is_globalptr="false" is_list="false" is_key="true" />
<FIELDFORMAT name="arrival" datatype="datetime" is_subobject="false" is_globalptr="false" is_list="false" is_key="false" />
....

This says that objects named "Transport" are tasks (is_task="true"). It's first field is named "id" and it is of type "string."

This file must be written by hand. There are many examples in the GLMTrans project.

Custom code

1) Override VishnuPlugIn.createXMLizer and make it return your XMLizer. Typically this is a subclass of CustomDataXMLizer.
2) Override CustomDataXMLizer.processTask and processAsset to send the fields of the tasks and assets you wish to send.
Nested objects, lists, and all the other Vishnu datatypes can be sent. For example, here's a snippet from a GLMTrans plugin:

protected boolean processTask (Object object, Object taskOrAsset) {
super.processTask (object, taskOrAsset);
Task task = (Task) taskOrAsset;

dataHelper.createDateField(object, "arrival", UTILPreference.getBestDate(task));
....

This will attach a field arrival of type date to the task being sent to Vishnu. The dataHelper is an object that allows you to send either XML or directly create Vishnu objects, depending on the setting of the runDirectly flag. If runDirectly is false, it will generate XML that looks like:
<OBJECT type="Transport">
....
<FIELD name="arrival" value="2001-09-21 13:00:00"/>
....

There are many example implementations of custom bridges in the GLMTrans society.

Automatic Translation

The translation from Cougaar objects to Vishnu XML is done directly. Two XML formats are created for Vishnu : the XML that describes the object format or meta-data and the object data itself. The Cougaar objects are traversed twice, once to create the object format XML and once to create the data XML. (These two XML formats are described separately.) A Format XMLizer traverses the Cougaar objects to create the format XML and a Data XMLizer traverses these same objects again to create the data XML.

Post processing - The Format and Data XMLizers perform some post processing to give unique names to types and fields that have the same name in the corresponding Java object. For instance, a preposition can have any type of object as an indirect object, so the bridge must figure out what types of indirect objects are present on the tasks and give them separate, unique field names. In addition, commonly used property groups are given unique names and turned into global data. These shared property groups are referenced by name in the tasks and resources.

Other notes:

The creation of these wrapup and setup tasks is slightly different for each plugin flavor. For expanders, a one-to-one expansion becomes a one-to-two expansion if one of the specs is defined, and one-to-three if both are. For aggregators, the MP task created by the aggregation is expanded. And for allocators, there is a one-to-two or three expansion, and each subtask gets allocated to the assigned resource.

Assignment Freezing

There is another facility provided by the bridge for expanders and aggregators. Since resource availability is represented in the role schedule, and since the role schedule does not reflect an assignment until an allocation is made, there is a gap of time between when an assignment is returned and when the resource's availability reflects the assignment. During this period, a new task could come in and be scheduled against the asset during the interval of a previous assignment. To protect against this, expanders and aggregators freeze task assignments until the plugin detects, through the allocation result, that an allocation has been made against the asset. Once this happens, the assignment is unfrozen and can be cleared from the Vishnu database.
Note : This facility is only active in batch mode.

Parameters

There are a number of parameters set in the Cluster's env.xml file that affect the behavior of the bridge.

Appendix D: DTD for XML

The following is a DTD showing the expected XML data formats for specifying a problem. (It is available as a text file in testdata/problem.dtd.)
 

<?xml version='1.0' encoding='UTF-8' ?>
<!-- Vishnu Problem Specification -->

<!ELEMENT PROBLEM (DATAFORMAT, SPECS, GAPARMS, (DATA)?)>
<!ATTLIST PROBLEM
          name CDATA #REQUIRED >

<!-- sets up the object formats, i.e. metadata -->
<!ELEMENT DATAFORMAT (OBJECTFORMAT)*>
<!ELEMENT OBJECTFORMAT (FIELDFORMAT)*>
<!ATTLIST OBJECTFORMAT
          name CDATA #REQUIRED
          is_task (true|false) #REQUIRED
          is_resource (true|false) #REQUIRED >
<!ELEMENT FIELDFORMAT EMPTY>
<!ATTLIST FIELDFORMAT
          name CDATA #REQUIRED
          datatype CDATA #REQUIRED
          is_subobject (true|false) "false"
          is_list (true|false) "false"
          is_key (true|false) "false"
          is_globalptr (true|false) "false" >

<!-- sets up scheduling specifications -->
<!ELEMENT SPECS (OPTCRITERION|DELTACRITERION|BESTTIME|CAPABILITY|
                 TASKDURATION|SETUPDURATION|WRAPUPDURATION|PREREQUISITES|
                 TASKUNAVAIL|RESOURCEUNAVAIL|CAPACITYCONTRIB|CAPACITYTHRESH|
                 GROUPABLE|TASKTEXT|GROUPEDTEXT|ACTIVITYTEXT|COLORTESTS)*>
<!ATTLIST SPECS
          direction (minimize|maximize) "minimize"
          multitasking (none|grouped|ungrouped|ignoring_time) "none"
          setupdisplay (left|right|line|color) "left"
          wrapupdisplay (left|right|line|color) "right"
          taskobject CDATA #IMPLIED
          resourceobject CDATA #IMPLIED >
<!ELEMENT OPTCRITERION (OPERATOR|LITERAL) >
<!ELEMENT DELTACRITERION (OPERATOR|LITERAL) >
<!ELEMENT BESTTIME (OPERATOR|LITERAL) >
<!ELEMENT CAPABILITY (OPERATOR|LITERAL) >
<!ELEMENT TASKDURATION (OPERATOR|LITERAL) >
<!ELEMENT SETUPDURATION (OPERATOR|LITERAL) >
<!ELEMENT WRAPUPDURATION (OPERATOR|LITERAL) >
<!ELEMENT PREREQUISITES (OPERATOR|LITERAL) >
<!ELEMENT TASKUNAVAIL (OPERATOR|LITERAL) >
<!ELEMENT RESOURCEUNAVAIL (OPERATOR|LITERAL) >
<!ELEMENT CAPACITYCONTRIB (OPERATOR|LITERAL) >
<!ELEMENT CAPACITYTHRESH (OPERATOR|LITERAL) >
<!ELEMENT GROUPABLE (OPERATOR|LITERAL) >
<!ELEMENT TASKTEXT (OPERATOR|LITERAL) >
<!ELEMENT GROUPEDTEXT (OPERATOR|LITERAL) >
<!ELEMENT ACTIVITYTEXT (OPERATOR|LITERAL) >
<!ELEMENT OPERATOR (OPERATOR|LITERAL)* >
<!ATTLIST OPERATOR
          operation CDATA #REQUIRED >
<!ELEMENT LITERAL EMPTY >
<!ATTLIST LITERAL
          value CDATA #REQUIRED
          type (constant|variable) #REQUIRED
          datatype CDATA #REQUIRED >
<!ELEMENT COLORTESTS (COLORTEST)* >
<!ELEMENT COLORTEST (OPERATOR|LITERAL) >
<!ATTLIST COLORTEST
          color CDATA #REQUIRED
          obj_type CDATA #REQUIRED
          title CDATA #REQUIRED >

<!-- sets up genetic algorithm specifications -->
<!ELEMENT GAPARMS (GAOPERATORS) >
<!ATTLIST GAPARMS
          pop_size CDATA #REQUIRED
          parent_scalar CDATA #REQUIRED
          max_evals CDATA #REQUIRED
          max_time CDATA #REQUIRED
          max_duplicates CDATA #REQUIRED
          max_top_dog_age CDATA #REQUIRED
          report_interval CDATA #IMPLIED
          initializer CDATA #REQUIRED
          decoder CDATA #REQUIRED >
<!ELEMENT GAOPERATORS (GAOPERATOR)+ >
<!ELEMENT GAOPERATOR EMPTY >
<!ATTLIST GAOPERATOR
          name CDATA #REQUIRED
          prob CDATA #REQUIRED
          parms CDATA #IMPLIED >

<!-- sets up data -->
<!ELEMENT DATA ((CLEARDATABASE|FREEZEALL|UNFREEZEALL)?, WINDOW?,
                NEWOBJECTS?, CHANGEDOBJECTS?, DELETEDOBJECTS?,
                (FREEZE|UNFREEZE)*) >
<!ELEMENT CLEARDATABASE EMPTY >
<!ELEMENT FREEZEALL EMPTY >
<!ELEMENT UNFREEZEALL EMPTY >
<!ELEMENT FREEZE EMPTY >
<!ATTLIST FREEZE
          task CDATA #REQUIRED
          resource CDATA #IMPLIED
          starttime CDATA #IMPLIED
          endtime CDATA #IMPLIED >
<!ELEMENT UNFREEZE EMPTY >
<!ATTLIST UNFREEZE
          task CDATA #REQUIRED >
<!ELEMENT DATA (CLEARDATABASE?, WINDOW?, NEWOBJECTS?,
                CHANGEDOBJECTS?, DELETEDOBJECTS?) >
<!ELEMENT CLEARDATABASE EMPTY >
<!ELEMENT WINDOW EMPTY >
<!ATTLIST WINDOW
          starttime CDATA #IMPLIED
          endtime CDATA #IMPLIED >
<!ELEMENT NEWOBJECTS (OBJECT|GLOBAL)* >
<!ELEMENT CHANGEDOBJECTS (OBJECT|GLOBAL)* >
<!ELEMENT DELETEDOBJECTS (OBJECT|GLOBAL)* >
<!ELEMENT GLOBAL (OBJECT) >
<!ATTLIST GLOBAL
          name CDATA #REQUIRED >
<!ELEMENT OBJECT (FIELD)* >
<!ATTLIST OBJECT
          type CDATA #REQUIRED >
<!ELEMENT FIELD (OBJECT|LIST)? >
<!ATTLIST FIELD
          name CDATA #REQUIRED
          value CDATA #IMPLIED >
<!ELEMENT LIST (VALUE)* >
<!ELEMENT VALUE (OBJECT)? >
<!ATTLIST VALUE
          value CDATA #IMPLIED >

• An ACTIVITY tag/object is only sent to the web server.
• All IMPLIED attributes are only sent to the web server.
• For either grouped or ungrouped multitasking, both ASSIGNMENT objects and MULTITASK objects are sent to the web server. For ungrouped multitasking, only ASSIGNMENT objects are sent to a client, while for grouped multitasing, only MULTITASK objects are sent to a client.

<?xml version='1.0' encoding='UTF-8'?>
<!-- Vishnu Assignments Specification -->

<!ELEMENT ASSIGNMENTS (ASSIGNMENT|MULTITASK|ACTIVITY)*>

<!ELEMENT ASSIGNMENT EMPTY>
<!ATTLIST ASSIGNMENT
          task CDATA #REQUIRED
          resource CDATA #REQUIRED
          setup CDATA #REQUIRED
          start CDATA #REQUIRED
          end CDATA #REQUIRED
          wrapup CDATA #REQUIRED
          frozen CDATA #IMPLIED
          color CDATA #IMPLIED
          text CDATA #IMPLIED >

<!ELEMENT MULTITASK (TASK)*>
<!ATTLIST MULTITASK
          resource CDATA #REQUIRED
          setup CDATA #REQUIRED
          start CDATA #REQUIRED
          end CDATA #REQUIRED
          wrapup CDATA #REQUIRED
          color CDATA #IMPLIED
          text CDATA #IMPLIED
          capacities CDATA #IMPLIED
          capacities_used CDATA #IMPLIED >
<!ELEMENT TASK EMPTY>
<!ATTLIST TASK
          task CDATA #REQUIRED >

<!ELEMENT ACTIVITY EMPTY>
<!ATTLIST ACTIVITY
          resource CDATA #REQUIRED
          start CDATA #REQUIRED
          end CDATA #REQUIRED
          color CDATA #IMPLIED
          text CDATA #IMPLIED >
 

Appendix E: Sample Problems

Job-Shop Scheduling Problem (testdata/jobshop/mt06.vsh)

The classic NxM research problem is as follows. There are M machines and N manufacturing jobs to be completed. Each job has M tasks/stages, with each stage corresponding to a different specified machine. There is a specified order in which the tasks for a certain job must be performed, with one task not able to start until the previous task has ended. The criterion to minimize is the makespan, which is defined as the end time of the last task completed. (Note that this research problem bears little resemblance to the problem that real job shops face. Unlike other systems, our reconfigurable scheduler can be easily modified to the constraints of a particular real-world job shop.)

The resources for this problem are of type machine, and the tasks for this problem are of type step. The metadata for these two object types are:

The color specifications are:
 

Traveling Salesman Problem (testdata/TSP/bays29.vsh)

The traveling salesman problem is as follows. There is a salesman who needs to start at a given city, travel to a set of other cities visiting each city once, and then return to the starting city. The distances from any city to any other city is provided. The objective is to minimize the total distance traveled.

There are two different approaches we have used to configure Vishnu for the traveling salesman problem. Both approaches consider each city other than the starting city to be a task. The first approach considers starting from the starting city to be a zero-duration task that must be performed first and returning to the starting city to be a task that must be performed last. The second approach (which is probably the superior one) instead has the setup time for the first city calculate its distance automatically from the starting city and has a wrapup time for the last city based on distance to the starting city. We use the second approach for the vehicle routing problem (which is largely just a multiple traveling salesman problem) because it extends easily to the multiple salesman case. So, we provide the first approach here to provide more variety.

The resource for this problem is of type salesman, and the tasks for this problem are of type city. The metadata for these two object types are:

Vehicle Routing Problem with Time Windows (testdata/VRP/solomon101.vsh)

The vehicle routing problem with time windows (VRPTW) is an extension of the capacitated vehicle routing problem (CVRP). In CVRP, there are M vehicles and N customers from whom to pick up cargo. Each vehicle has a limited capacity for cargo, and each piece of cargo contributes different amounts towards this capacity. Each vehicle that is utilized starts at a central depot, makes a circuit of all its customers, and then returns to the depot. The objective is to minimize the total distance traveled by the vehicles. In VRPTW, an extra constraint is added that there is a certain window of time in which each pickup must be initiated. The pickups require a certain non-zero time (for loading of the cargo).

The resources for this problem are of type vehicle, and the tasks for this problem are of type customer. Another object type, extradata, holds all the global data. The metadata for these object types are:

Generalized Assignment Problem (testdata/assignment/c515-1.vsh)

The generalized assignment problem is not a true scheduling problem in that there are no times associated with the assignments of tasks to resources. There are N jobs to be assigned to M agents. There is a predefined set of assignment costs associated, one associated with each pairing of a job and an agent. Each agent also has a defined capacity, and each job contributes a defined amount towards the capacity of each agent (with this amount depending on the agent). The objective is to maximize the total costs. The metadata are:

Appendix F: Installation and Setup Procedure

Goal: Install an apache web server (DSO), with php4, which talks to mysql & gd.

Versions:
mysql-3.22.32-pc-linux-gnu-i686.tar.gz (Binary) (USE Gnu tar !!!)
apache_1.3.14
php-4.0.3pl1
zlib-1.1.3
libpng-1.0.8
jpeg-6b
gd-1.8.3

Assumptions: Linux box. (Not too differant) Install to /usr/local/* from /usr/local/src/*

mysql binary:
% su # Become root.
% cd /usr/local # location of mysql dir
% gzip -dc mysql-VERSION-OS.tar.gz | tar xvf -
% ln -s mysql-VERSION-OS mysql
% cd mysql
% ./scripts/mysql_install_db
% ./bin/safe_mysqld & # FOR TESTING

# System startup...
% cp support-files/mysql.server /etc/rc.d/init.d # (Lose rc.d for Solaris)
% chmod 755 /etc/rc.d/init.d/mysql.server
# -> Create links in rc3.d to start/stop the server.

# Start server.
# -> Kill safe_mysqld
% /etc/rc.d/init.d/mysql.server start # (Lose rc.d for Solaris)

# Set the root password.
% /usr/local/mysqladmin -u root password abc123
% /usr/local/mysql/bin/mysql -u root -pabc123 mysql
mysql> USE mysql
mysql> UPDATE user SET Password=password('abc123') WHERE User='root';

zlib:
% cd /usr/local/src/
% gzip -dc zlib-1.1.3.tar.gz | tar xvf -
% cd zlib-1.1.3
% ./configure
% make
% make install

libpng:
# Note: zlib MUST already be built.
% cd /usr/local/src
% gzip -dc libpng-1.0.8 | tar xvf -
% cd libpng
% cp scripts/makefile.linux Makefile # Choose appropriate make file.
% make
% make install

jpeg:
% cd /usr/local/src
% gzip -dc jpeg-6b.tar.gz | tar xvf -
% cd jpeg-6b
% ./configure
% make
% make install

gd (Depends upon libpng and jpeg):
% cd /usr/local/src
% gzip -dc gd-1.8.3.tar.gz | tar xvf -
% cd gd-1.8.3
# Read Makefile
% make
% make install

Apache 1.3.14
% cd /usr/local/src
% gzip -dc apache_1.3.14.tar.gz | tar xvf -
% cd /usr/local/src/apache_1.3.14
% ./configure \
   --prefix=/usr/local/http-80 \
   --with-layout=Apache \
   --enable-rule=SHARED_CORE \
   --enable-module=so \
   --enable-module=info \
   --enable-module=rewrite \
   --enable-module=headers \
   --enable-module=usertrack
% make
% make install

PHP4
% cd /usr/local/src
% gzip -dc php-4.0.3pl1.tar.gz | tar xvf -
% cd /usr/local/src/php-4.0.3pl1
% cat INSTALL # !!!!
% vi /etc/ld.so.conf
vi> Add: /usr/local/lib
vi> Add: /usr/local/mysql/lib
% ldconfig
% rm config.cache
% ./configure \
   --with-apxs=/usr/local/http-80/bin/apxs \
   --with-mysql=/usr/local/mysql \
   --with-zlib=/usr/local/ \
   --with-gd=/usr/local/ \
   --with-jpeg-dir=/usr/local/bin \
   --with-libpng=/usr/local/ \
   --with-config-file-path=/usr/local/lib \
   --with-xml \
   --enable-track-vars

% make
% make install
% cp php.ini-dist /usr/local/lib/php.ini # To path specified above.
# Notes: --with-zlib, --with-jepeg-dir --withlibpng are all questionable.

Configure Apache:
% cd /usr/local/http-80/config
% vi httpd.conf
- Change/Uncomment:
DirectoryIndex index.html index.htm index.shtml index.cgi index.php index.php3 index.phtml
AddType application/x-httpd-php .html .php .php3 .phtml
AddType application/x-httpd-php-source .phps
- Other non-php configs...
ie: hostname, cgi, includes, logs, ...
- Group -> www
% /usr/local/http-80/bin/httpd -t # Test the syntax of the the config files.

# System startup...
% cd /etc/rc.d/init.d (/etc/init.d for Solaris)
% ln -s /usr/local/http-80/bin/apachectl httpd-80
% ../rc3.d
% ln -s ../init.d/httpd-80 S80httpd-80
% cd ../rc5.d
% ln -s ../init.d/httpd-80 S80httpd-80
% cd ../rc1.d
% ln -s ../init.d/httpd-80 K15httpd-80
% cd ../rc2.d
% ln -s ../init.d/httpd-80 K15httpd-80
% cd ../rc6.d
% ln -s ../init.d/httpd-80 K15httpd-80
# - Remove the existing apache S and K files if needed.
# - Stop the old server if running.
# - Start the new server.
# - Check Errors in /usr/local/http-80/logs/errors

Misc:
# Create a local 'www' group.
# Let the userver run as nobody.www.
# Change dir permissions.
# Give acces to trusted users.
#--
% vi /etc/group
www:x:8080:foouser,baruser
% cd /usr/local
% chgrp -R www mysql
% chgrp -R www http-80
% cd /usr/local/http-80
% chmod 775 htdocs
% chmod u+s htdocs

Sources:
Apache 1.3.14 - http://www.apache.org/dist/apache_1.3.14.tar.gz
PHP v. 4.0.3pl1 - http://www.php.net/downloads.php
Zlib - ftp://ftp.uu.net/graphics/png/src/zlib-1.1.3.tar.gz
Gd - http://www.boutell.com/gd/http/
MySQL - http://www.mysql.com/downloads/index.html
Libpng - http://www.libpng.org/pub/png/src/libpng-1.0.8.tar.gz
JPEG-6b - http://cygutils.netpedia.net/V1.1/jpeg-6b/jpegsrc.v6b.tar.gz

Dependancies:
We have used Sun's Java 1.2.2 as our environment. This code is available from Sun's Javasoft web site. The other component of the Java environment that Vishnu requires is an XML Java library. We have used the Xerces library available at this web site. For convenience, we have included the same xerces.jar file you would get from this site in the Vishnu package in the directory lib. After either downloading xerces.jar or copying it from lib, you must add its full path to your CLASSPATH environment variable.

The tar file vishnu.tar.gz contains code/files that go in three different places.

1. The php and sql directories go on the web server. The sql directory can go anywhere, but the php directory should go somewhere, or be linked to from somewhere, that is visible via the web server. Perhaps the best way to do this on a UNIX machine is to type

> ln -s <fullpath>/php </home/httpd>/html/vishnu
where <fullpath> is the full pathname of the parent directory of php and </home/httpd> should be replaced with the home directory of Apache if /home/httpd is not the home directory.
2. The vishnu.jar file should go on whatever machines are executing the server and/or compiler. On these machines, make sure to add/vishnu.jar to your CLASSPATH environment variable.
3. The testdata directory should go on whatever machine is going to be used for running the web browser for testing the system.

To start the automated scheduler, execute the command
java -Dvishnu.host=[hostname] -Dvishnu.path=[pathname] -Dvishnu.user=[username] -Dvishnu.password=[password] -Dvishnu.port=[portnumber] org.cougaar.lib.vishnu.server.Scheduler
Start the formula compiler with the same command with ExpressionCompiler substituted for Scheduler. Note that it is best to make a small script file for starting the scheduler and compiler. Some examples of such script files are given in the scripts directory. Also note that the defaults are hostname=[localhost], path="/~vishnu/", user=vishnu, password="", and portnumber=80.

You should now be set up to run.

Vishnu is still in its early stages. There are many improvements to be made and holes to be filled. Here is a list of some of the enhancements we are considering:

• Manual Assignments - The user should be able to perform an assignment or unassignment of a task to a resource.
• Better Capacity Logic - The current logic does not allow for resetting of capacity (due to unloading or the end of a time interval).
• Synchronization of Multiple Clients - There should be better locking of database tables to ensure that no inconsistencies arise when we start using multiple clients, particularly multiple schedulers.
• Sparse Distance Matrices - The user should be able to specify distances only between nearby locations, and the scheduler should be able to fill out the full set of distances between a set of locations by finding minimum paths through the network.
• Rollback for Data Error - When there is an error loading data, the database should roll back to a state where it was consistent rather than be in an inconsistent state. This will necessitate using Berkeley BDB tables to provide rollback capability. Remember to delete the problem name if there is an error loading the problem definition.
• Access Control and Security - We should use https instead of http for greater security. We should consider defining the concept of privileges so that certain users can perform certain operations and access certain problems. We should consider some way of better hiding the username and password used by the scheduler and compiler.
• Schedule Stability Soft Constraint - It should be possible to express a preference for keeping the schedule the same as much as possible without freezing the assignments.
• Automatic Freezing of Past Assignments - The automated scheduler should automatically not modify any assignment earlier than the start of the scheduler window.
• Geographic Display - For those problems where the tasks have associated geographic data (latlongs or xy_coords), we should provide a way to view this data graphically.
• Evaluation of Specs in Browser - To allow debugging of scheduler specifications, provide a way for the user to evaluate a formula for a constraint in a desired context (i.e., with the variables and assignments set appropriately).
• Recheck Constraints for Frozen Tasks - Instead of just assigning the frozen task to the same resource with the same start and end time, first check to make sure that the task is still of the same duration, that the task is still available, that the resource is still available, etc. Updating the frozen assignments can get complicated if the effects ripple into other frozen assignments.
• User-selectable Alerting - Using formulas, let the user define certain conditions under which he or she wants to be alerted. Generally, this will be when the assignment (or lack of assignment) for a particular task is far enough from the ideal to warrant human intervention.
• Display reference field - The key field for tasks and resources that provides a unique internal reference is also used for referencing these objects in the display. We should consider adding an option for a separate (or additional) field for referencing these objects in the display.
• Command-Line Compiler - Currently, there is now way to execute the compiler without the web server. We should implement something analogous to the internal scheduler so that the compiler can be run from a command line.
• Runtime Check of Legality of Specs - Since data structures may have changed since the last compilation of the scheduling specifications, do a quick check before scheduling that the specs are still legal.
• Resource Utilization Display - Make functional again the code that displays the fraction of the resources and their capacities used as a function of time.

Appendix G: Documentation Notes

The original document was embedded in php.  All php information has been removed for ease of editting.

The Sample problems in Appendix E need reworking to correct errors and make easy to understand

Developed using Netscape Composer 4.77

Written by Talib Hussain, based upon earlier documentation written by Gordon Vidaver

Copyright 2001 BBN Technologies
Version: October 12, 2001