|
|
Vishnu User's Guide
I. Introduction
I.1 What is Vishnu?
Vishnu is a reconfigurable, web-based, optimizing scheduling system. It
performs scheduling in the sense that it assigns tasks to resources at
particular times. It is reconfigurable in that it is capable of being configured
purely by data specifications and not by recoding to handle a wide range
of different scheduling problems with different scheduling semantics. It
is optimizing insofar as it allows the specification of a criterion for
evaluating how good a legal schedule is and will try to find a schedule
that is as good as possible (in many cases actually finding an optimal
or near optimal schedule). It is web-based since the GUI runs completely
from a browser and since all interactions with the central database are
via a web server. The graphical interface allows the user to define
Vishnu problems using the point-and-click interface afforded by today's
web browsers.
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
Vishnu delivers its capabilities through the use of a web server front-end
and a genetic algorithm back-end. To use Vishnu, and for this tutorial,
you do not need to know details of what genetic algorithms are and how
they work. But, a brief introduction is provided <here> if you
wish to familiarize yourself with some of the basics. The web-server
front-end has a visual interface (see vishnu.bbn.com/vishnu/vishnu.php
) that allows a user to manually specify a scheduling problem and submit
it for optimization. The web-server can also be used seamlessly as
a service to a domain-dependent scheduling application. That application
may submit problems directly to the web-site, initiate the optimization
and extract the resulting solutions. All without the user ever looking
at the web-site. To properly design such an application, the <Vishnu
API> and the <Vishnu XML problem format> must be understood. The
API is currently in Java, but instructions on how to access the web-server
directly are provided <here>. User of ALP may use the Couggar-Vishnu
Bridge to quickly design an interface to Vishnu for their problems.
I.3 What is a Scheduling Problem in Vishnu?
The goal of Vishnu is to solve a given scheduling problem by finding the
best possible way of assigning tasks to resources
over time. The assigning of a task to a resource basically involves "reserving"
that resource for the particular task for a particular contiguous time
interval. In a basic Vishnu problem, a single task may reserve only
a single resource (for a single time interval) and a single resource may
be reserved by multiple tasks over time. The total picture: multiple
tasks assigned to multiple resources at various time intervals, with no
overlapping and with no unassigned tasks. We'll call this a schedule.
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?
Vishnu is capable of solving any problem which involves the allocation
of instances of a single type of task to instances
of a single type of resource for contiguous intervals of time. Given
a particular real-world problem, the user of Vishnu must conceptualize
that problem in terms of allocating a set of similar tasks to a set of
similar resources. This modelling step may require some initial effort
since it may require a slight change in the normal way of viewing that
scheduling problem in its domain. One must also be very clear about
what constraints are to be used to define a legal schedule. Vishnu
has been designed to allow a variety of dependencies and constraints to
be specified, and future work will extend these capabilities even further.
Finally, for Vishnu to be capable of performing an optimization, the user
must quantify the criteria that are to be used to determine how good a
particular schedule is. This is another step that may require a change
in mind-set since the original problem may have been optimized manually
used vague criteria or rough rules-of-thumb. Once the problem can
be modelled as above, it remains to enter the appropriate data and logic
into Vishnu.
Scheduling Problem: Job-Shop Scheduling
Many classic scheduling problems have a natural formulation that is easily
specified in and solved by Vishnu. For example, consider the classic
Muth-Thompson NxM job-shop scheduling research problem (JSS). There are
M machines and N manufacturing jobs to be completed. Each job consists
of a chain of M steps. Each step of a job is assigned to a different
specified machine and requires the exclusive use of that machine for a
given duration. No two steps of a job are assigned to the same machine.
There is a specified order in which the steps for a certain job must be
performed, with one step unable to start until the previous step has ended.
The criterion to minimize is the makespan, which is defined as the
end time of the last step completed.
Can JSS be solved by Vishnu? Recall the two basic modelling steps
that are required:
a. Represent the problem in terms of one type of task and one type of
resource.
-
Here we have multiple machines and multiple jobs, each with multiple steps.
Which should be a task and which should be a resource? The obvious
answer is that the steps of a job should be the "tasks" and the machines
should be the "resources". The idea is that a job step "reserves"
the machine, and that multiple steps (of different jobs) wish to do this.
-
But, we have several dependencies that must be included, namely that the
steps of each jobs must be processed in a specific order. This type of
dependency (requiring one or more tasks to be the pre-requisite of another
task) is supported in Vishnu, so we are set - each successive step of a
given job can be assigned the previous step as a pre-requisite. Between
jobs there are no dependencies.
b. Develop clear criteria for evaluating how good a particular solution
is.
We wish to minimize the final completion time of the last step on the
schedule. This requires a simple lookup of the latest completion
time of all scheduled tasks.
|
Scheduling Problem? : Travelling Salesperson Problem
Many other problems, such as general optimization problems, may
not at first glance seem like something that can be solved by Vishnu.
These problems may require a shift or two in mind-set to specify and solve
them in Vishnu. For example, consider the popular Travelling Salesperson
Problem (TSP). There is a salesperson that needs to start at a given
city, travel to a set of other cities, visiting each city exactly once,
and then return to the starting city. The distance from any city
to any other city is known. The objective of TSP is to minimize the
total distance travelled.
Can TSP be solved by Vishnu? Recall the two basic modelling steps
that are required:
a. Represent the problem in terms of one type of task and one type of
resource.
-
Here we have multiple cities and a single salesperson. Which should
be a task and which should be a resource? If we considered the salesperson
to be the "task" and the cities to be "resources", then a Vishnu scheduling
problem would involve scheduling the salesperson to a single city and we
would be done. Not what we are looking for. If we consider
the cities to be the "tasks" and the salesperson to be the "resource",
then a Vishnu scheduling problem would involve scheduling all the cities
in various orders to the saleperson. This sounds better. The
idea is that a city "reserves" the salesperson, and that multiple cities
wish to do this.
-
But, what about the idea in Vishnu of allocating based upon "time"?
TSP involves the use of distance, not time. Can we model TSP in Vishnu?
Yes. It simply requires us to assume that each unit of distance takes
a unit of time. Drawing the equality between time and distance reflects
a change in "mind-set" as mentioned earlier. So, we define a resource
allocation as: a given city will reserve a salesperson for an amount of
time equal to the distance between that city and the previous one in the
schedule. This type of dependency (making the time interval of one
element of a schedule dependent upon the previous element) is supported
by Vishnu, so we are set.
-
And, we have one final dependency that we must include: the final city
must be the same as the start city. This requires a bit of finesse
in our thinking. Since it is impossible to schedule the same task
twice in a given schedule in Vishnu, we must represent the starting city
as two separate tasks - first and last. To ensure that
first
is the initial element of the schedule and last is the final element,
we must include appropriate dependencies into the problem. For example,
we can require that first must occur before every other task and
we can require that every other task must occur before last.
This type of dependency (requiring one or more tasks to be the pre-requisite
of another task) is supported in Vishnu, so we are set.
b. Develop clear criteria for evaluating how good a particular solution
is.
We wish to minimize total distance travelled. Given our equality
of time with distance, we thus wish to minimize the total time used.
The best schedule will have the lowest end-to-end time for the usage of
the salesperson.
|
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.
Creating a scheduling problem in Vishnu requires the following
steps (not necessarily in order):
-
Defining a task type
-
Defining a resource type
-
Defining global type(s)
-
Defining a set of logic rules
-
Creating task instances
-
Creating resource instances
-
Creating global instances
|
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
Vishnu provides a variety of predefined atomic types and
predefined
object types that may be used when creating the user-defined data
types (i.e., task types, resource types and global types). The predefined
types in Vishnu are:
-
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
Vishnu requires that the user define a task type and a resource type, and
provides the capability to define an arbitrary number of global types.
In creating each of these user-defined types, the following syntax rules
apply:
-
All user-defined types must have unique names.
-
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
-
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.
-
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.
-
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
-
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.
A pointer to a global type (or global pointer) allows an
instance (A) of one object type to refer to an instance (B) of another
object type. This reference is made by entering the name of the target
instance (i.e., B) in the appropriate field of the referring instance (i.e.,
A).
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
Once types have been defined, instances of those types must created to
store the appropriate information for the problem. When creating
instances, the following syntax rules apply:
-
All task instances must have a unique KEY value.
-
All resource instances must have a unique KEY value.
-
These are permitted to be the same as the KEY values of task instances.
-
Global instances may be instances of a predefined object type or of a user-defined
global type.
-
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.
-
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
-
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).
-
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.
We illustrate this syntax by expanding upon our earlier TSP example.
| Travelling Salesperson Problem:
We add two global types to our earlier example: TV_Show
and City_Stats. We also add two new fields to our task type.
The 'most_watched_show' field is a global pointer to a TV_Show instance.
The 'statistics' field is an encapsulated object of type City_Stats.
City
(task type) |
Salesperson
(resource type) |
TV_Show
(global type)
|
City_Stats
(global type)
|
| Field
Name |
Field
Type |
| name |
string |
| index (KEY) |
number |
| distances |
list |
| preceding_cities |
list |
| most_watched_show |
global ptr to TV_Show |
| statistics |
City_Stats |
|
| Field
Name |
Field
Type |
| name (KEY) |
string |
|
| Field
Name |
Field
Type |
| name |
string |
| networks |
list of string |
|
| Field
Name |
Field
Type |
| founding_date |
datetime |
| location |
latlong |
| population |
number |
|
Sample Cities:
A set of task instances, resource instances, and global instances
are provided. Note that the global instance 'Friends' is pointed
to by several task instances.
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 |
|
| most_watched_show |
Friends |
| statistics.founding_date |
1790-01-01 00:00:00 |
| statistics.location |
39N 77W |
| statistics.population |
572059 |
|
|
Field Name
|
Field Value
|
| name |
Boston |
| index |
2 |
| distances |
440, 0, 217, 440 |
| preceding_cities |
1 |
| most_watched_show |
Friends |
| statistics.founding_date |
1630-01-01 00:00:00 |
| statistics.location |
42N 71W |
| statistics.population |
589141 |
|
|
Field Name
|
Field Value
|
| name |
New York |
| index |
3 |
| distances |
225, 217, 0, 225 |
| preceding_cities |
1 |
| most_watched_show |
Star Trek |
| statistics.founding_date |
1664-01-01 00:00:00 |
| statistics.location |
41N 73W |
| statistics.population |
8008278 |
|
|
Field Name
|
Field Value
|
| name |
Washington D.C. |
| index |
4 |
| distances |
0, 440, 225, 0 |
| preceding_cities |
1, 2, 3 |
| most_watched_show |
Friends |
| statistics.founding_date |
1790-01-01 00:00:00 |
| statistics.location |
39N 77W |
| statistics.population |
572059 |
|
Fred
(resource instance)
|
Friends
(global instance)
|
Star Trek
(global instance)
|
Ally McBeal
(global instance)
|
|
Field Name
|
Field Value
|
| name |
Fred Smith |
|
|
Field Name
|
Field Value
|
| name |
Friends |
| networks |
nbc |
|
|
Field Name
|
Field Value
|
| name |
Star Trek: Next Generation |
| networks |
abc, nbc, fox |
|
|
Field Name
|
Field Value
|
| name |
Ally McBeal |
| networks |
fox |
|
Logic Rules (incomplete):
Prerequisites: task.preceding_cities |
II.2.4 Keyword Variables
As we will see later, a logic rule requires access to certain information
about the Vishnu problem in order to perform meaningful computation.
To accomodate this, Vishnu has certain keyword variables
that are predefined. Not all keyword variables are available to all
logic rules. (Note: currently there is no restriction that avoids
an instance having the same name as a keyword variable. unknown effects
and potential logical errors in rule design may occur, especially in novices
- who may feel compelled to explicitly define such 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)
Note, these could have been defined as functions in the Vishnu specification
language described in the next section, but are provided as keywords for
ease of use when designing logic rules.
II.3 Vishnu Specification Language
Underlying the specification of logic rules in Vishnu is a simple functional
language reminiscent of LISP called the Vishnu specification language,
which includes predefined functions and operators.
II.3.1 Basic Functions
The Vishnu specification language includes a variety of basic predefined
functions that may be used when designing logic rules to manipulate data.
That data will be from the task instances, resource instances, and global
instances and may be of predefined or user-defined type.
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.
| Function |
Data
Types |
Description |
| Variable Binding Functions |
|
|
| withvar |
(String,
type1, type2)
| The result of evaluating the second parameter is bound to the variable name provided by the first parameter. In computing the third parameter, the variable name may be used directly to refer to its value. (e.g., withvar("foo",5*3,foo+foo*foo)). Provides important efficiency properties (especially if the middle argument is complex and must be used multiple times in the third argument).
|
| Boolean Functions |
|
|
| if |
(boolean,
type,
<type>) => type |
If the first
argument is true, returns the second argument; otherwise, the third argument
(or null) |
| and |
(boolean,
<boolean>, ?) => boolean |
Logical
and of arguments |
| or |
(boolean,
<boolean>, ?) => boolean |
Logical
or of arguments |
| not |
(boolean)
=> boolean |
Logical
not of argument |
| hasvalue |
(type)
=> boolean |
Returns
true if the argument is not null |
| Math Functions |
|
|
| mod |
(number,
number) => number |
Remainder
when dividing the first argument by the second argument |
| abs |
(number)
=> number |
Absolute
value of a number |
| max |
(number,
<number>, ?) => number or
(datetime, <datetime>, ?) => datetime |
Maximum
value of arguments |
| min |
(number,
<number>, ?) => number or
(datetime, <datetime>, ?) => datetime |
Minimum
value of arguments |
| Creation Functions |
|
|
| string |
(type)
=> string |
Convert
any object into a string |
| latlong |
(number,
number) => latlong |
Return a
latlong object with latitude and longitude set to the first and second
arguments respectively |
| xy_coord |
(number,
number) => xy_coord |
Return a
xy_coord object with x and y set to the first and second arguments respectively |
| interval |
(datetime,
datetime, <string>, <string>) => interval |
Return an
interval object with start and end times set to the first and second arguments
and label1 and label2 set to the third and fourth arguments |
| list |
(<type>,
<type>,
?) => list |
Makes a
list out of all the arguments |
| append |
(string,
string) => string or
(list, list) => list |
Appends
two strings/lists into a longer string/list |
| Access Functions |
|
|
| dist |
(latlong,
latlong) => number or
(xy_coord, xy_coord) => number |
Returns
the distance (in nautical miles if using latlong's) between the two arguments. (Note, to convert from nautical miles to miles, must multiply by conversion factor 1.1507795) |
| entry |
(list, number)
=> type |
Returns
the ith element (starting from 1) of the list, where i is the
second argument |
| matentry |
(matrix,
number, number) => type |
Returns
the i-jth element (starting from 1) of the matrix, where i and
j are the second and third arguments |
| length |
(list) =>
number |
Returns
the length of a list |
| find |
(list, string,
boolean) => type |
Returns
the first element in the list such that when the variable named by the
second argument is set to this element the boolean expression given by
the third argument is true |
| position |
(list, type)
=> number |
Returns
the first position in the list (with the first element being 1) of the
given element |
| contains |
(list, type)
=> boolean |
Returns
true if the given list contains the given object.
|
| Iteration Functions |
|
|
| loop |
(number,
string,
type) => list |
Iterates,
setting the variable named by the second argument equal to all integers
between 1 and the first argument inclusive, accumulating the third argument
into a list |
| mapover |
(list, string,
type)
=> list |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, accumulating the value of the third argument
into a new list |
| sumover |
(list, string,
number) => number |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, summing the values of the third argument |
| maxover |
(list, string,
number) => number |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, maximizing over the values of the third argument |
| minover |
(list, string,
number) => number |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, minimizing over the values of the third argument |
| andover |
(list, string,
boolean) => boolean |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, doing a logical and of the values of the third
argument |
| orover |
(list, string,
boolean) => boolean |
Iterates
over each element of the first argument, setting the variable given by
the second argument to it, doing a logical or of the values of the third
argument |
Table 1. Basic Functions
II.3.2 Task Functions
The Vishnu specification language includes a number of predefined functions
that are used to access and manipulate task instances. Each of these
functions accepts parameters that are known to be task instances (i.e.,
passing predefined atomic/object data, global instances or resource instances
will cause an error).
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.
| Function |
Data
Types |
Description |
| findtask |
(list, string)
=> task |
Return the
task in a list whose key is equal to the second argument |
| taskstarttime |
(task) =>
datetime |
Returns
the assigned start time of a task, or null if not yet assigned |
| taskendtime |
(task) =>
datetime |
Returns
the assigned end time of a task, or null if not yet assigned |
| tasksetuptime |
(task) =>
datetime |
Returns
the assigned time for the start of the setup period of a task, or null
if not yet assigned |
| taskwrapuptime |
(task) =>
datetime |
Returns
the assigned time for the end of the setup period of a task, or null if
not yet assigned |
| resourcefor |
(task) =>
resource |
Returns
the resource assigned to a task, or null if not yet assigned |
| formersetuptime |
(task) =>
datetime |
Returns
the setup time for a task after a temprary assignment. Ideal for use in computation of differences in setup time of the "next" task after a given task during computation of delta criterion. Returns null if the task does not exist or is not yet assigned |
| formerwrapuptime |
(task) =>
datetime |
Returns
the wrapup time for a task after a temporary assignment. Ideal for use in computation of differences in
wrapup time of the "next" task after a given task during computation of delta criterion. Returns null if
the task does not exist or is not yet assigned |
| taskstoredcontrib |
(task, number) =>
number |
Returns
the #th (#=second parameter) capacity value that has been stored for the given task in its current assignment. Generally use #=0 unless capacity is a vector. Returns null if the task does not exist, or if the task has not yet been assigned (or if # is out-of-bounds). |
| capacitycontrib |
(task, number) =>
number |
Similar to taskstoredcontrib, but recomputes the capacity contribution value using the CapacityContribution rule. If second parameter is not given, returns the first element of the capacity vector (i.e., same as number = 0).
Returns null if the task does not exist, or if the task has not yet
been assigned. (May cause error is second parameter is out-of-bounds.) |
| taskprevioustask |
(task) =>
task |
Returns the task that is assigned immediately before the given task on the same resource, or null if no such task or if given task is null or unassigned. |
| nexttask |
(resource, datetime) =>
task |
Returns the next task that is assigned to the given resource after the given datetime (i.e., starttime is strictly greater than given time). Returns null if no such resource or if no task has been assigned after the given time. |
| currenttask |
(resource, datetime) =>
task |
Returns the current task that is assigned
to the given resource at the given datetime (i.e., the task-starttime <= datetime <= task-endtime)
Returns null if no such resource or if no task has been assigned at the given time. |
Table 2. Task Functions
II.3.3 Resource Functions
The Vishnu specification language includes a number of predefined functions
that are used to access and manipulate resource instances. Each of
these functions accepts parameters that are known to be resource instances
(i.e., passing predefined atomic/object data, global instances or task
instances will cause an error).
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.
| Function |
Data
Types |
Description |
| findresource |
(list, string)
=> resource |
Return the
resource in a list whose key is equal to the second argument |
| tasksfor |
(resource)
=> list |
Returns
the list of tasks assigned to this resource |
| numtasks |
(resource)
=> number |
Returns
the number of tasks assigned to this resource, or null if the resource does not exist |
| complete |
(resource)
=> datetime |
Returns
the time when a resource has finished all its assignments |
| busytime |
(resource,
<datetime>, <datetime>) => number |
Returns
the number of seconds that a resource has spent performing tasks in the
time interval between the second and third arguments (or for all time) |
| preptime |
(resource)
=> number |
Returns
the number of seconds that a resource has spent doing setup and wrapup |
| previousdelta |
(resource)
=> number |
Returns
the sum of all delta evaluations for all the tasks already assigned to
a resource |
| lasttask |
(resource)
=> task |
Returns
the last task currently assigned to the given resource, or null if the resource is null or if no task has been assigned to the resource
|
| firsttask |
(resource)
=> task |
Returns
the first task currently assigned to the given resource, or null if the resource is null or if no task has been assigned to the resource
|
| isavailable |
(resource, datetime, datetime)
=> boolean |
Returns
true if the given resource if available between the two given datetimes. Assumes that the first datetime is less than or equal to the second. inclusive of start, exclusive of end. If datetimes are null, assigns min.max possible value, as appropriate. Returns null if the given resource is null.
|
Table 3. Resource Functions
II.3.2b Misc Functions
| Function
| Data
Types |
Description |
| tasknamed |
(String) =>
task |
Returns
the task that has the given String as its name (i.e., key). Returns null if no such task exists. |
| resourcesfor |
(task) =>
list |
Returns
the list of resources to which this task is assigned, or null if not yet assigned |
| midnight |
(datetime) =>
datetime |
Returns
the datetime representing midnight on the same day (earlier) as the given datetime. Daylight savings is preserved. |
| addclock |
(datetime, number) =>
datetime |
Returns
the datetime resulting from adding the given number of seconds to the given datetime. However, Daylight Savings is "preserved" -- if the second parameter is 86400, which normally represents "24 hours" and
it crosses a time zone boundary, then the value returned is adjusted accordingly.
Thus, 8am + 24 hours = 8 am (not 7 or 9 due to daylight savings start/end). Returns null if either parameter is null. |
| dayname |
(datetime) =>
String |
Returns
the name of the day associated with the given datetime (e.g., "Monday", "Tuesday", etc)
|
| midnight |
(datetime) =>
datetime |
Returns
the datetime representing midnight on the same day (earlier) as the given datetime. Daylight savings is preserved. |
| get |
|
|
| globget |
|
|
| groupfor |
|
|
| committedresource |
|
|
| commitmentlevel |
|
|
| committedtime |
|
|
| varintervals |
|
|
| fixedintervals |
|
|
| threshold |
|
|
| vishnutime |
|
|
| vishnulocaltime |
|
|
| todate |
|
|
| toduration |
|
|
| argminover |
|
|
| argmaxover |
|
|
Table 3b. Misc Functions
II.3.4 Operators
In addition to the predefined functions above, the Vishnu specification
language includes a set of arithmetic and comparison 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.
Comparison operators are (=, !=, <, <=, >, >=), which 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.
II.4 Vishnu Constraints and Logic Rules
II.4.1 Expressions
Now that we have a basic understanding of the data types and specification
language available in Vishnu, we have the necessary tools to finish the
design of a Vishnu problem. At the heart of the reconfigurability
of the Vishnu scheduler is the ability of the user to specify the behavior
of the scheduler. There are a variety of different types of problem constraints
that can be specified. A few of these constraints are simply multiple
choice among a set of options. However, most of these constraints
are specified as a logic rule. Vishnu allows the user to define 17
different logic rules. Each logic rule is a single expression.
Expressions involve the following types of components:
-
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)
Thus, a logic rule could be an expression that is: a constant value; an
access to (a data field of) a keyword variable; an access to a data field
of a global instance; or a compound expression that uses functions and
operators to produce a single result. Each of the 17 possible logic
rules represents a value that is used by the Vishnu optimization system
in a fixed manner. Each logic rule has a default expression, which
the user may override by defining a new expression. Default values
for each logic rule are given so that a user does not need to specify an
expression for all logic rules. In the following sections, all the
logic rules are explained. To properly understand their place in
the Vishnu system, some of the underlying algorithms used in Vishnu are
described at a high level.
II.4.2 Genetic Algorithm
Vishnu is an reconfigurable scheduler that is based upon a genetic algorithm
search component and a greedy scheduling component. The logic rules
of Vishnu allow the user to modify certain behaviours of both components.
Basic knowledge of genetic algorithms and greedy algorithms is assumed
in the following discussion.
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.
| Constraint |
Type |
Variables |
Default
Value |
Description |
| Optimization
Criterion |
number |
|
0 |
Numerical
value indicating how good the current schedule is |
| Optimization
Direction |
multiple
choice |
N/A |
minimize |
Must
be either minimize or maximize |
| Prerequisites |
list
of strings |
task |
empty
list |
Names
of all the tasks that must be scheduled before scheduling task |
Table 4. Genetic Algorithm Constraints
II.4.3 Greedy Scheduler
The majority of the logic rules pertain to the behaviour of the greedy
scheduler. The greedy scheduler iterates performing the following
procedure until all tasks are scheduled (or deemed unscheduled).
-
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.
-
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.
-
Evaluate how good each assignment is
-
Keep the assignment to that resource that is the best (i.e., perform a
greedy selection of resource).
The greedy scheduler uses several logic rules to clarify exactly what is
meant by each of the highlighted actions above.
-
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.
-
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.
-
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.
-
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.
-
Starting at best-time, find the next non-zero, available interval after
best-time.
-
For that interval, temporarily assign A to that interval. Generally,
A will be slotted in between two tasks previous and next.
-
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).
-
If A can still fit in between previous and next, we have
found a valid interval.
-
If A does not fit, return to step a and continue until a valid interval
is found
-
Repeat, searching for a valid interval before best-time.
-
Return the valid interval that is closest to best-time.
-
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.
| Dependencies between Setup Duration / Core Duration / Wrapup Duration:
The dependencies between durations of tasks next to each other in the
schedule may be illustrated conceptually as follows: Let us say that
we are assigning drives (tasks) to busses (resources). Let us consider
3 drivers (tasks): Bob, George, and Anne. Let us simplify things
with only a single bus. Now, let us pretend that George and Bob like
to play practical jokes on each other, but that Anne is very proper and
doesn't stand for any of that nonsense.
Let us define task setup as involving: Finding where the bus is parked
and starting it up.
Let us define task wrapup as involving: Parking the bus and stopping
it.
The bus is supposed to always be parked in the same spot near the school,
and Anne won't tolerate otherwise. But, George and Bob like to park
the bus as far away as possible - but only if they know the next driver
won't be Anne. Parking close takes time C, and parking far away takes
time F. Finding the bus when close takes 0 time, but finding it when
far takes X time.
Driving the bus route always takes D time, for simplicity.
The bus always starts and end in its correct spot.
Now, if we schedule the drivers in the following order: G, B,
A, we know that the following will happen:
before Bob:
G = 0 + D + C
A = 0 + D + C
After inserting Bob:
G = 0 + D + F
B = X + D + C
A = 0 + D + C
But if we schedule drivers in the order A, B, G
Before Bob:
A = 0 + D + C
G = 0 + D + C
After inserting Bob:
A = 0 + D + C
B = 0 + D + F
G = X + D + C
Note that the placement of B in the middle of A and G has a different
effect on everyone's timings as compared to placement in the middle of
G and A.
|
Other Logic Rules:
-
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.
-
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.
-
Linked/Link Time Difference
| Constraint |
Type |
Variables |
Default
Value |
Description |
| Delta
Criterion |
number |
task,
resource |
0 |
Incremental
contribution to optimization criterion introduced by having resource perform
task |
| Best
Time |
datetime |
task,
resource, duration |
start_time |
Optimal
time for the task to begin |
| Capability |
boolean |
task,
resource |
true |
Whether
resource has the required skills to perform task |
| Task
Duration |
number |
task,
resource |
0 |
How
many seconds it takes resource to perform task |
| Setup
Duration |
number |
task,
previous, resource |
0 |
How
many seconds it takes resource to prepare to perform task if it last performed
previous |
| Wrapup
Duration |
number |
task,
next, resource |
0 |
How
many seconds it takes resource to clean up after doing task if it will
be performing next |
| Task
Unavailability |
list
of intervals |
task,
resource, prerequisites, duration |
empty
list |
All
intervals of time when task cannot be scheduled (label1 and label2 fields
ignored) |
| Resource
Unavailability |
list
of intervals |
resource |
empty
list |
All
intervals of time when resource is busy (label1 and label2 can be used
for text and color) |
| Capacity
Contribution |
number
or
list of numbers |
task |
0 |
How
much task contributes towards filling each type of capacity |
| Capacity
Threshold |
number
or
list of numbers |
resource |
0 |
How
much capacity of each type that resource has |
| Multitasking |
multiple
choice |
N/A |
none |
Ability
of resources to perform more than one task at a time (must be none
, ungrouped , grouped
, or ignoring_time ) |
| Groupable |
boolean |
task1,
task2 |
true |
Whether
task1 and task2 can be done as part of the same group (should be reflexive
and transitive) |
| Linked |
boolean |
task1,
task2 |
false |
Whether
the start time of task2 is linked to the start time of task1 |
| Link
Time Difference |
number |
task1,
task2 |
0 |
Number
of seconds that the start time of task2 must follow the start time
of task1 |
Table 5. Scheduling Constraints
| Constraint |
Type |
Variables |
Default
Value |
Description |
| Task
Text |
string
or
number or boolean |
task |
"" |
Text to
put in box for task on the schedule graphic |
| Activity
Text |
string
or
number or boolean |
interval |
"" |
Text to
put in box for the activity associated with interval on the schedule graphic |
| Grouped
Tasks Text |
string
or
number or boolean |
tasks
(overloaded) |
"" |
Text to
put in box on the schedule graphic for the given group of tasks performed
simultaneously |
| Task
Color (one for each possible color) |
boolean |
task |
false |
Whether
task should be displayed in the given color on the schedule graphic |
| Activity
Color (one for each possible color) |
boolean |
interval |
false |
Whether
activity of interval should be displayed in the given color on the schedule
graphic |
| Grouped
Tasks Color (one for each possible color) |
boolean |
tasks
(overloaded) |
false |
Whether
the set of grouped tasks should be displayed in the given color on the
schedule graphic |
| Setup
Display |
multiple
choice |
N/A |
left |
Must be
left (left diagonal striping), right (right diagonal striping), line (single
dotted line), or color (use color specs) |
| Wrapup
Display |
multiple
choice |
N/A |
right |
Must be
left (left diagonal striping), right (right diagonal striping), line (single
dotted line), or color (use color specs) |
Table 6. Graphical Display Constraints
II.4.4 Logical Debugging
There are two mechanisms in place to ensure that expressions are robust
under evaluation. The first is type checking, which is performed by the
expression compiler. All the components of a expression are checked to
validate that they are returning the right type for their context, including
making sure that the entire expression returns the correct type for its
constraint. (The correct type associated with a particular constraint is
given in Table 1.)
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
See 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
eit |
