|
|
Frequently Asked Questions
What is Vishnu? Vishnu is an optimizing reconfigurable scheduler plus a web-based system for defining the problems for the scheduler to solve and viewing the results of the scheduler. What is scheduling? Scheduling is deciding how to allocate one or more scarce resources. These resources are allocated in order to accomplish particular tasks. Usually, but not always, the resources are allocated to the tasks for limited intervals of time. (Scheduling problems that do not consider time are often instead referred to as assignment problems.) What is optimized scheduling? In most well-defined scheduling problems, there are hard constraints (i.e., constraints that absolutely must be satisfied) and soft constraints (i.e., constraints that can be violated but at a cost). If the problem is even moderately difficult, there will be no way to adhere to all the soft constraints, and therefore tradeoffs will have to be made. Combining the costs incurred by all the different violations of soft constraints gives a measure of how good a particular schedule is. Optimized scheduling searches the space of all possible legal schedules for one that comes as close as possible to being the optimal with respect to this cost function. What is a reconfigurable scheduler, and what is so good about it? Most schedulers solve a limited class of scheduling problems in a single domain. A reconfigurable scheduler greatly widens the the range of problems that the scheduler can solve and can work in any domain. For example, a reconfigurable scheduler can just as easily schedule taxi cab pickups as soccer fields, just as easily schedule classrooms for test as crews to fly airplanes, just as easily schedule jobs in a flexible factory as calls for repairpeople. The flexibility to tailor a reconfigurable scheduler to your problem of interest is what makes it so powerful. Why is it named Vishnu? The Hindu god Vishnu is the preserver. He acts whenever the good and evil in the world become unbalanced in order to restore the balance. Like Vishnu, our scheduler considers many different factors and attempts to optimally balance the tradeoffs between them. How did Vishnu get started? Vishnu was developed as part of the DARPA's Advanced Logistics Program (ALP). The ALP program manager, Todd Carrico, challenged us to develop a generic (i.e., reconfigurable) scheduler for use with Cougaar, an infrastructure developed under ALP for building multiagent systems. The goal was that a non-programmer should be able to set up a Cougaar agent to do scheduling. We designed Vishnu to work either as a standalone scheduler or as part of Cougaar. What are the components of Vishnu? There are three components of Vishnu: the web server, the automated scheduler and the formula compiler. The web server, backed by a relational database, is at the center of it all. It provides the data exchange mechanism between all the other pieces (automated scheduler, formula compiler, human users, and external clients), as well as the data for the web browsers that provide the graphical interface. The automated scheduler does the optimized scheduling. The formula compiler translates from easily readable formulas to a form usable by the scheduler. A more in-depth description and an architecture diagram are provided in Section 2 of the full documentation. How do I install Vishnu and get it running? Appendix D of the full documentation provides a full description of the installation and setup of Vishnu. In brief, the steps are as follows:
I now have Vishnu installed. How do I get started? The best way to get started with Vishnu is to start playing with the sample problems. In the directory testdata, there are a variety of files which can be loaded into the web server using the Upload function on the home page. You can recognize the loadable files by their vsh extension. Try running the scheduler on them and looking at the results. Then try changing the scheduling specifications and rerunning the scheduler and see how the results change. Don't worry about messing up the problems; you can always reload them again from file. When you understand the sample problems, then try making a problem of your own. Section 6 of the full documentation is good to read if you prefer to start by reading rather than by playing. I am now ready to define a problem of my own. How do I do it? There are three ways to define a problem. The first is to use a web browser. How to do this is described in Section 6 of the full documentation. A second approach is to load a problem definition from a file. How to do this loading is described in Section 6 of the full documentation. You can create such a file either by saving a problem that you have created or by creating it from scratch using the format described in Appendix B of the full documentation. A third way to define a problem is to have an external client feed the problem definition to the web server. You either need to write your own external client or else utilize the Cougaar-Vishnu bridge How do I save a problem to file for future use or for loading on another server? On the problem page, there is a Download link. If you click here, you will be given four different options of what to save. If you select "Problem definition and data", everything (metadata, scheduling specs, and data) gets saved. This is also described in Section 6 of the full documentation. Can I run Vishnu without a web server? Yes, you can run just the automated scheduler portion of Vishnu independent of the web server. There is an internal mode which allows you to invoke the scheduler directly from a Java application. However, there are three important caveats. First, without the web server you will be unable to graphically view the results. Second, this currently requires you to have compiled (XML) versions of the scheduling specs, which means that you should have first set up the problem using the full web-based system (since the compiler does not run without the web server). Third, because you must invoke the scheduler from a Java application, you must either have the expertise to write such an application or else use the Cougaar-Vishnu bridge. Can I run more than one automated scheduler with a single web server? Yes, multiple schedulers can accept problems from a single web server. Having multiple schedulers is particularly useful when they are running on different computers or CPUs, so that you get the benefits of parallel execution. Why must there be a single object type for tasks and a single object type for resources? The formula compiler must know what type of object each task and resource is going to be in order to be able to do its consistency checks and ensure that the formulas make sense. What happens if I have resources (or tasks) of different object types? There are three different options, and the right solution depends on the problem. One possible solution is to divide the problem into independent separate problems, with each subproblem handling one type of resource. Another possible solution is to divide the problem into interconnected subproblems, with the connection implemented using the Cougaar multiagent infrastructure and the Cougaar-Vishnu bridge. A third solution is to define a single "superobject" that contains the data fields from the different object types plus a field that tells which type of underlying object each superobject actually is. How do scheduling specifications work? The scheduling specs are executed by the scheduler at different points during its execution. For example, to determine the list of all resources that can perform a given task, the scheduler will execute the Capability Criterion formula with task set to the given task and resource set to each of the resources in succession. You tailor the logic of the scheduler for your problem using these specs. How do I go about developing a good set of scheduling specifications for my problem? The development of scheduling specifications is an iterative process. In general, you should not expect to get them correct the first time. You should have one or more test problems available to evaluate the schedule produced by a particular set of specifications. Start with your first attempt at the specifications. Run with the current specs on the test problem(s), analyze the results, determine what needs to be improved, and edit the specs to accomplish this. Iterate through this process until you get good results. Save the specs to file when you have ones you like. What are the genetic algorithm parameters, and how do I know how to choose them? The description of what each paramter does is given in this table in the full documentation. The best choices for these values vary greatly depending on the problem. Sometimes there is any easy answer. For example, if there is no contention for resources (i.e., no two tasks would prefer to be assigned to the same resource at overlapping time intervals), then the best solution has a maximum evaluations of 1, hence taking the guaranteed optimal schedule generated by the first individual. However, often it is not obvious what the best values for the parameters are, and some experimentation may be required. How can I optimize the performance of the Vishnu scheduler? There are two different measures of performance: (i) speed and (ii) quality of the schedule. There is generally a tradeoff between these two measures; by running the scheduler longer the genetic algorithm can find better solutions. So, one way to optimize performance is to make sure that the genetic algorithm parameters are set to make the optimal tradeoff with respect to your needs. A second way to optimize performance is to make the formulas in the scheduling specifications as simple as possible. The setup and wrapup duration specifications get executed particularly frequently and so should be the object of particular attention. A third way to optimize performance is to reduce the amount of data being fed to the scheduler. This can be accomplished by eliminating any unused data fields and by using global pointers for any large blocks of data that are repeated across many tasks and/or resources. A fourth approach
is to use the scheduler in internal mode, hence avoiding the
data transfer overhead involved in going through the web server.
The down side of this is that you will not be able to see the
results using the web server.
A second reason is that the symbolic approach we have developed
for expressing constraints is more intuitive to those not
trained in mathematics and computer programming. This is
important if we hope to eventually reach a large user community. |
|
