Scheduling with a processing time oracle
This page contains programs which were used to conduct experiments, documented in the paper "Scheduling with a processing time oracle", by Dufossé, Dürr, Trystram and Vásquez.
Don't hesitate to contact us if you have some difficulties to use them.
- adaptive.cpp: permits to explore the game tree for various instances with fixed number of jobs and given maximal parameters p and x. Checks the two phase conjecture and generates two dimensional picture representing the equilibrium schedules depending on the different values of p and x. This picture can be visualized with the program plot_tmp.py.
critical.py: Has the same functionalities as the previous C++ program, but in addition can conduct the computations using fractions and hence avoid all rounding errors, plot the game tree, or compute the equilibrium schedule using the polynomial time algorithm proposed in our paper, rather than by exploring the game tree.
- The computations made in Mathematica to analyse the stop ratio: Notebook, pdf.
non adaptive model
non_adaptive.py: Similar functionalities as the previous program, but for the non adaptive model.
- The computations made in Mathematica to analyse the asymptotic ratio: Notebook, pdf.