Instances for Position-Dependent Maintenance Scheduling
M.Drozdowski, F.Jaehn, R.Paszkowski
General information
File format
The instances
Contact
General Information
This page comprises datasets (instances) 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:
- the number of jobs n,
- frequency of maintenances k,
- 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
- the number of maintenance operations,
- 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 format
Instances
The 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-1
instance 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.
Solutions
Values 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 isOPT
file 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.
Test Instances
Contact
