old program
Attic for old programs

-- I didn't know what to do with it anymore, so I put it on the web.

Classical scheduling algorithms

Maximal feasible job set, or 1||ΣU
Algorithm by Hogdson
Schedule in round robin fashion, for P|pmtn|Cmax
Algorithm by Mc Naughton
Graham's 4/3-approximation for makespan on parallel machines, or P||Cmax
Algorithm by Graham
Single Scheduling of Equal-Length Jobs to Minimize the Average Flow Time, or 1|rj;pj=p;Dj|ΣC
Algorithm by Garey, Johnson, Simons, Tarjan
2-approxmation by scheduling in order of Smith ratio, for 1|rj;pmtn|Σ wjCj
Algorithm by Smith analyzed by Goemans, Wein, Williamson.
Preemptive scheduling of equal length jobs with release time on two machines to minimize flow time
Algorithm by Herrbach and Leung
Multimachine Scheduling of Equal-Length Jobs to Minimize the total weighted Flow Time, or P|rj;pj=p;Dj|Σ wjCj
Algorithm by Brucker and Kravchenko
Minimum energy speed scaling scheduling
Algorithm by Yao, Demers, Shenker
Computing the maximum flow (yes, I know, it is not a scheduling problem)
Algorithm by Ford and Fulkerson

Our scheduling algorithms

Other useful tools

Does my LP have fractional optima?
In python mainly [doc+source]
The tools used to create the pages above
The man in the middle
permits to trace a TCP connexion
In Java [doc+source]
Expression evaluator
This simple applet evaluates numerical expression.
In Java [applet]
Filter for contex-free grammars, which outputs an equivalent grammar, where (1) every non-terminal can be reached from the start symbol, (2) every non-terminal can produce a word containing only terminals.
In C++ using the standard template library [doc+source]
A brute force simulator for Quantum Turing Machines.
In C++ using some now old version of the LEDA library. [more].