This website is a supplement for the paper titled, “Windows Scheduling of Arbitrary Length Jobs on Multiple Machines”.
by Amotz Bar-Noy, Richard E. Ladner, Tami Tamir, and Tammy VanDeGrift
Below are links to sample files showing results of running the original algorithm proposed in the paper. Two types of instances were generated for scheduling: non-perturbed instances were created from leaves of randomly created trees; perturbed instances were created by changing the values of the width and length in the leaves (W, L) such that the total difference of the sum of L/W values did not exceed one. The motivation for creating the perturbed instances was to create a test samples that had less consistent-sized jobs while knowing the optimal number of machines on which to schedule the instances.
For each of the sample files below, the optimal number of machines is 100. The number and size of jobs varied. The orignal algorithm was executed to find the number of machines in which to schedule the (W, L) jobs. In all cases below, the algorithm found close to the optimal number of machines (within 3 machines or within 3% of optimal).
|Optimal Number of Machines||Number of Machines Produced by Algorithm||Number of Jobs||Perturbed (P) or Non-perturbed (NP)||File|