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|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_jC_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_jC_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

Our scheduling algorithms

• 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

Other useful tools

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].