Title: SPEED ROBUST SCHEDULING SUPPLEMENTAL MATERIAL
Authors: Franziska Eberle · Ruben Hoeksma · Nicole Megow · Lukas Nölke · Kevin Schewior · Bertrand Simon
Categories: Applied Mathematics, Computation Theory and Mathematics
Item type: Software
Keywords: Scheduling algorithm, Computer-assisted proof
Description:
This supplemental material proves two claims of the main paper named "Speed-Robust Scheduling".
File list:
- BricksUnderSand.nb, BricksUnderSand.pdf: Mathematica sheet and its output, proving the last claim of Lemma 11
- check.py: Python script used to certify that for the relevant values of number of machines and unit-size jobs, there exists a 4/3-robust solution (Lemma 15). Must be in the same folder as results.json, file which is currently compressed in results.json.zip
- results.json.zip: compressed data file containing the input of the script check.py
- Results.txt: contains human-readable data represented in results.json.zip. Each data point is an instance of a scheduling problem accompanied by a solution expliciting an upper bound on the competitive ratio.
The "results" data was produced using a Mathematica ILP solver.
The method to reproduce the results claimed follows:
1) - unzip the file results.json.zip to results.json.
- run check.py using Python (version 3.8.10 used).
- A successful execution proves that the cases needed in Lemma 15 are proved.
2) - the pdf file BricksUnderSand.pdf displays the function claimed to be positive in Lemma 11. You can run the Mathematica sheet (version 11.0 used) BricksUnderSand.nd to reproduce the result.
References: https://arxiv.org/abs/2011.05181
License: CC BY 4.0