DOI: 10.5281/zenodo.17427117
title: Instances for Position-Dependent Maintenance Scheduling

description: This dataset comprises instances, and information on solutions, for the problem of preemptive scheduling n jobs with ready times rj, due dates dj, and processing times pj, on a single machine subject to maximum lateness Lmax. Moreover, after at most k job changes on the machine a nonpreemptive maintenance operation of duration s must be executed.

Five series of the instances have been generated.

The first three series of instances were created to conduct experiments on algorithms sensitivity to:

1. the number of jobs -- n,

2. frequency of maintenances -- k,

3. the duration of the maintenances -- s.

In each of the series, a range of the tested parameter was swept while the remaining parameters were randomized. For example, in the tests with changing n, we set n=1 and the remaining parameters were generated randomly. In this way 100 instances with n=1 were constructed. Instances for n = 1,2,5,10,20,50,100 were generated in such a way. The instances for k=1,2,5,10,20,50,100 and for s=1,2,5,10,20,50,100,200,500,1000 were constructed analogously.

The next two series of instances were generated to test the impact of

4. the number of maintenance operations,

5. the duration of the maintenances s.

on the number of preepmtions. In these two series n=16.

More on the problem, instance generation, conducting the tests and the analysis of the obtained results can be found in:M.Drozdowski, F.Jaehn, R.Paszkowski, Scheduling position-dependent maintenance operations, Operations Research 65(6), 2017, 1657–1677,  doi: 10.1287/opre.2017.1659.

 File formatInstancesThe structure of a file with test instances is as follows:

instance id;k;s;n;[pmtn]0;r0;p0;d0...n-1;rn-1;pn-1;dn-1instance id;k;s;n;[pmtn]...

where:instance id - is the instance number within the file;k,s,n - are frequency of maintenance, duration of the maintenance, number of jobs;[pmtn] is the number of preemptions for problem 1|rj,pmtn|Lmax; it is present only in tests series 4., 5., (pmtnk and pmtns) related to the number of preemptions;0...n-1 - are job indexes within the instance;rj;pj;dj - are job j ready time, processing time, due date.

In series 1.-3. each file comprises 10 instances. In the 4th series the number of instances per file is 3-5. In the 5th series the number of instances per file is 13. SolutionsValues of Lmax for a given series of instances are provided in one file. The results are in the format:

file n k s Lmax Lower bound is OPT?0 n0 k0 s0 Lmax0 LB0 isOPT...9 n9 k9 s9 Lmax9 LB9 isOPTfile n k s Lmax Lower bound is OPT?...

where:file - is the name of the file with instances, the rest of this line is just a header guiding the eye when reading;0...9 - each line starts with the id of the instance in the original instance file;nj,kj,sj - repeat the original n, k, s of the instance j;Lmaxj - is the best known maximum lateness for the instance;LBj - is the biggest lower bound for the instance;isOPT="Opt" - states that the obtained value of the maximum lateness is optimum.

The solution files are collected in one zip-ped archive solutions.zp. The test instance files and the corresponding solutions files are:




1.
vsn.zip 
vsn-solutions.txt 


2.
vsk.zip 
vsk-solutions.txt 


3.
vss.zip 
vss-solutions.txt 


4.
pmtnk.zip 
pmtnk-solutions.txt 


5.
pmtns.zip 
pmtns-solutions.txt