How to make a web-interface for a scheduling program

Step 1 : write the scheduling program

The main ingredient is a program, that takes the scheduling instance as command line arguments and prints a schedule in text form. For example

$ ./minEnergy.py "1/1/2 3/1/4 0/2/5" 2
<schedule numberjobs= 4  numbermachines=1  makespan= 10  objvalue= 0  objfct=energy >
<execution job=0 machine=0 start=1 end=2 />
<execution job=2 machine=0 start=2 end=3 />
<execution job=1 machine=0 start=3 end=4 />
<execution job=2 machine=0 start=4 end=5 />
<job name=0 releasetime=1 processingtime=1 deadline=2 />
<job name=1 releasetime=3 processingtime=1 deadline=4 />
<job name=2 releasetime=0 processingtime=2 deadline=5 />
</schedule>

The program above is in python, but could be written in any language, as long as it is compiled on the webserver, or on a machine with an identical architecture.

Ususally I encode the instance in the form "releasetime/processingtime/deadline" for every job, and number them in the order they appear starting at 1. The parsing in the program is done very brutaly, I just replace all slashes by spaces and tokenize the string. This particular program above takes another number L as parameter, which is part of the scheduling instance. In general additional parameters could be the number of parallel machines for example, or other parameters depending on the particular scheduling problem.

A few words on the text format of the printed schedule. The first line contains something called "makespan". In the picture that will be produced from it, the time goes from 0 to this number, so you probably want to set it to the largest deadline in the input or the largest completion time or so.

The attributes "objvalue" and "objfct" are just to label the picture in the bottom left corner, but objvalue has to be a number. So if the scheduling instance happen to be infeasible, print "objvalue=0 objfct=feasiblity" and on the picture one can then read "feasibility=0".

The other lines describe execution slots and jobs with their releasetime-deadline interval. All numbers that represent time steps as "start", "end" "releasetime" can be floating point numbers.

For scheduling problems which do not have deadlines, just print any big number for a deadline.

You see that the job numbers and machine numbers start at zero here. Only the filter which produces a picture out of it will add 1 to these numbers.

If you want your program to print other additional informations other than this schedule you can use stderr for it.

Step 2: adapt the filter

What we do now is to produce a picture from the textual schedule that we got from the program above. This is done by a small program schedule2svg. Here is the source of it. It has been extended sevreral times, always a bit in the rush, so it is not particularly nicely written.

Sometimes you can use this program without modification, but sometimes you may need to adapt it. For example in some scheduling problems jobs have sizes, which represent the number of machines needed simultaneously for its execution. Then you want to extend somehow the text format of schedules and adapt the program schedule2svg to be able to read the new format.

The output is a picture in SVG format, which is very roughly a sort of XML version of PDF.

$ ./minEnergy.py "1/1/2 3/1/4 0/2/5" 2 | ./schedule2svg 
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="201" height="57" viewBox="0 0 201 57">
<text x="3" y="54" text-anchor="start">energy=0</text>
<rect x="18" y="3" width="18" height="15" style="fill:yellow;stroke-width:1;stroke:rgb(0,0,0)" />
<text x="21" y="15" text-anchor="start">1</text>
<rect x="36" y="3" width="18" height="15" style="fill:coral;stroke-width:1;stroke:rgb(0,0,0)" />
<text x="39" y="15" text-anchor="start">3</text>
<rect x="54" y="3" width="18" height="15" style="fill:pink;stroke-width:1;stroke:rgb(0,0,0)" />
<text x="57" y="15" text-anchor="start">2</text>
<rect x="72" y="3" width="18" height="15" style="fill:coral;stroke-width:1;stroke:rgb(0,0,0)" />
<text x="75" y="15" text-anchor="start">3</text>
<line x1="18" y1="19" x2="18" y2="36" style="stroke:grey"/>
<text x="21" y="36"  text-anchor="start">r1</text>
<line x1="54" y1="19" x2="54" y2="36" style="stroke:grey"/>
<text x="57" y="36"  text-anchor="start">r2</text>
<line x1="0" y1="19" x2="0" y2="36" style="stroke:grey"/>
<text x="3" y="36"  text-anchor="start">r3</text>
</svg>

The schedule2svg program has a few command-line parameters that can be combined:

zoom: will show the picture twice as large.
rows_are_jobs: The schedule will be shown with each job in its own row. The color of the execution slot represents then the machine. Without this parameter, each row corresponds to a machine, and the colors of the execution slots represent then the jobs.
both: Below the schedule, there is a row for every job showing its release time-deadline interval. The prefix in black shows the length of the processing time.
show_deadlines: The deadlines are also shown. The output can become a mess if several jobs have the same deadline or the same release time.

Step 3: create the actual image

Not all webbrowsers can show images in the SVG format, so we filter it through another program which converts SVG into PNG. This program is called convert and comes in the ImageMagic debian package. Usually when I launch it in the command line it prints "Segmentation fault". I have no idea why, and it is not important, since it nevertheless produces the correct image. So the picture above filtered through this program produces this output.

Step 4: combine in a PHP script

Fine, what we have to do now, is to combine all these programs in a php page called schedule.php and that has the following content.

<?

header('Content-type: image/png');
#header('Content-type: text/plain');

$jobs = $_REQUEST[jobs];
$L    = $_REQUEST[L];

echo `./minEnergy.py '$jobs' '$L' |  ./schedule2svg both | convert - png:- `; 

?>

The first line tells the webbrowser that the content of this page is an image. But if you don't see anything you might want to tell the browser that it is plain text, and remove some of the filters, so you can see what went wrong.

Step 5: The final webpage with a form

The last step is to create a webpage with a form, so we can edit the instance. Create a page index.php with the following content.

[...]
<h1>Preemptive Scheduling to Minimize Energy</h1>
We are given [...] gaps.
<p>

<?
 $jobs = $_REQUEST[jobs] ;
 $L    = $_REQUEST[L] ;

 if (!$jobs) {
     $n=10;
     for($i=0; $i<$n; $i+=2) {
       $a = rand(0,55);
       $b = rand(0,55);
       $p = rand(1,10);
       $r = min($a,$b);
       $d = max($r+$p,$a,$b);
       $jobs .=  "$r/$p/$d  ";       
     }
     $L = 10;
}
?>
<h2>Input</h2>
<p>
<form action=index.php>
<table>
<tr>
<td align=right>
release time/processing time/deadline for every job i
     <td><input name="jobs" size=60 value="<? echo $jobs; ?>">
<tr>
<td align=right>
Boot-time L
     <td><input name="L" size=60 value="<? echo $L; ?>">
</table>
<input type=submit value="Compute the schedule">
</form>
<p>
<h2>Output</h2>
<?
 echo "<img src=\"" . strtr("schedule.php?jobs=$jobs&L=$L"," ","+")."\">";
?>

Above you see a form, where the target page is the same page. So when you click on "submit" you can see your result, and continue editing the instance. The first part of the php script reads the parameters of the form into variables $jobs and $L. And if they are empty, it generates a random instance, so you see at least something when you arrive first on the page.

Then in the form it is important to use the content of these variables as default values for the text input boxes of the form. Otherwise clicking on "submit" would erase the form.

In the last part of this php script, an image-URL is created which copies the parameters $jobs and $L to the script schedule.php and there the spaces have to be replaced by pluses. But don't worry in the schedule.php script once the values are read with $_REQUEST[jobs], the pluses became again spaces.

Well, I hope this was clear.