Attic for old programs

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

- Maximal feasible job set, or 1||ΣU
- Algorithm by Hogdson
- Schedule in round robin fashion,
for P|pmtn|C
_{max} - Algorithm by Mc Naughton
- Graham's 4/3-approximation for makespan on parallel machines,
or P||C
_{max} - Algorithm by Graham
- Single Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,
or 1|r
_{j};p_{j}=p;D_{j}|ΣC - Algorithm by Garey, Johnson, Simons, Tarjan
- 2-approxmation
by scheduling in order of Smith ratio,
for 1|r
_{j};pmtn|Σ w_{j}C_{j} - 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~~Java Applets do not run anymore on modern browsers :-(- Multimachine Scheduling of Equal-Length Jobs to Minimize the total weighted Flow Time,
or P|r
_{j};p_{j}=p;D_{j}|Σ w_{j}C_{j} - 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~~

~~Generalized Whac-a-Mole~~~~Polynomial Time Algorithms for Minimum Energy Scheduling~~- Speedscaling Scheduling with powerdown states
- The Complexity of Mean Flow Time Scheduling Problems with Release Times or P|r
_{j};pmtn;p_{j}=p|Σ C_{j} - Multimachine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,
or P|r
_{j};p_{j}=p;D_{j}|Σ C_{j } - Scheduling tall and small unit length jobs
or P|r
_{j};p_{j}=1;size_{j}∈{1,m};D_{j}|- - Offline prefetching
- Runway scheduling with holding times
- Preemptive Scheduling of Equal-Length Jobs to Minimize the weighted number oj late jobs,
or 1|r
_{j};pmtn;p_{j}=p|Σ w_{j}U_{j}

- Does my LP have fractional optima?
- In python mainly [doc+source]
- The tools used to create the pages above
- [here]
- 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]- Gra2Reduc
- 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] - QTM
- A brute force simulator for Quantum Turing Machines.

*In C++ using some now old version of the LEDA library.*[more].