Experimental study of single machine scheduling problem for parameterized analysis

We report experimental data testing the robustness factor of variable parameters for single machine scheduling problem $1|r_j,q_j|C_{\max}$. We expose 3900 instances of the problem (file: instances.zip) with up to 50,000 jobs (although we tested over 50000 instances, in total, and selected 3900 "hardest" ones, i.e., ones maximizing our variable parameters, as we explain a bit later). Our instances were generated randomly according to the standard rules commonly used in the literature, except that we allowed different ranges for job processing times, with the upper limit for the intervals of job processing times from 3 to 181.

We also report the experimental data for 900 benchmark instances from [1], see statistics in Table (file: Benchmark_Instances_Table.pdf) and graphics Average1_1Jobs_Benchmark.pdf, Maximum1_1Jobs_Benchmark.pdf and Minimum1_1Jobs_Benchmark.pdf.

Our instances are grouped according to their sizes (the number of jobs) n, we explored instances of 26 different sizes from 10 to 50,000 jobs. For each size n, we used different values for the upper limit of the interval of job processing times: the limits 50 and 100 have been earlier used in literature; in addition we established upper limits maximizing our variable parameters. For each size n, we found these limits using a search in the range [1,500], up to 500 possible limits (about 1800 instances) for each size n. Then we created 50 instances for the so determined upper limit, and we created 50 instances also for limits 50 and 100.

The attached program (folder: code), is an implementation written in the language C++ of the corresponding procedure from the VP-Algorithm from [2] for counting the robustness factor of our variable parameters.

In the notation that we use in our tables and graphics,
$\rho_{1.1}$ is the robustness factor for the type 1.1 jobs. As we can see from (file: 1_2JobsTable.pdf), quite unexpectedly, the total number of type 1.2 jobs turned out to be neglectable for all the tested instances, independently of their size and the chosen upper limit for job processing times. At the same time, asymptotically, the variable parameter $\nu_{1.1}$ (the number of type 1.1 jobs) converges to 0 as the size of the instances increases, see graphics Average1_1Jobs.pdf, Maximum1_1Jobs.pdf and Minimum1_1Jobs.pdf.

References:

[1] Alonso-Pecina, F. A Code and Supplementary Data for a Hybrid Implicit Enumeration and Approximation Algorithm for Scheduling One Machine with Job Release Times and Due Dates (A Complement to the Manuscript “Fast Approximation for Scheduling One Machine”). Available online: https://github.com/FedericoAlonsoPecina/Scheduling

[2] N. Vakhania. Compact enumeration for scheduling one machine. Preprint available in arXiv, 2021. https://arxiv.org/abs/2103.09900