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

本研究报告了针对单机调度问题中变量参数鲁棒性因子的实验数据。我们对问题$1|r_j,q_j|C_{max}$进行了3900个实例的测试（文件：instances.zip），每个实例包含高达50,000个作业（尽管我们测试了超过50,000个实例，并从中选择了3900个“最难”的实例，即最大化我们的变量参数的实例，具体解释见后）。我们的实例是根据文献中常用的标准规则随机生成的，不同之处在于我们允许作业处理时间的范围不同，作业处理时间的上限区间为3至181。此外，我们还报告了900个基准实例的实验数据，来自文献[1]，详见表格（文件：Benchmark_Instances_Table.pdf）和图形文件Average1_1Jobs_Benchmark.pdf，Maximum1_1Jobs_Benchmark.pdf和Minimum1_1Jobs_Benchmark.pdf。我们的实例根据其规模（作业数量）n进行分组，我们探讨了从10到50,000个作业的26种不同规模的实例。对于每个规模n，我们使用了不同的作业处理时间上限值：50和100这两个上限在文献中已有使用；此外，我们还建立了最大化我们的变量参数的上限。对于每个规模n，我们使用[1,500]范围内的搜索来确定这些上限，每个规模n有高达500个可能的上限（约1800个实例）。然后，我们为每个确定的上限创建了50个实例，并为上限50和100创建了50个实例。所附的程序（文件夹：code）是用C++语言编写的，对应于文献[2]中VP-Algorithm的计数变量参数鲁棒性因子的相应过程。在我们表格和图形中所使用的符号中，$
ho_{1.1}$是1.1类型作业的鲁棒性因子。从（文件：1_2JobsTable.pdf）中我们可以看到，出人意料的是，对于所有测试的实例，无论其规模和选择的作业处理时间上限如何，1.2类型作业的总数都微乎其微。同时，随着实例规模的增加，变量参数$
u_{1.1}$（1.1类型作业的数量）趋向于0，详见图形Average1_1Jobs.pdf，Maximum1_1Jobs.pdf和Minimum1_1Jobs.pdf。