Windows Scheduling Experiment Samples


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
100
 101
 831
 NP
 nonpurturbedExample1.txt
100
 101
 735
 NP
 nonpurturbedExample2.txt
100
 101
 869
 NP
 nonpurturbedExample3.txt
100
 101
 817
 NP
 nonpurturbedExample4.txt
100
 102
 875
 NP
 nonpurturbedExample5.txt
100
 103
 691
 P
 purturbedExample6.txt
100
 102
 850
 P
 purturbedExample7.txt
100
 101
 863
 P
 purturbedExample8.txt
100
 102
 796
 P
 purturbedExample9.txt
100
 102
 932
 P
 purturbedExample10.txt