Structured versus Random Benchmarks for the Permutation FlowShop Scheduling
Problem
For most wellknown NPhard optimization problems, there are established
benchmarks suites that are used to compare the performance of approximation
algorithms. Very often, the problem instances in these benchmark suites
are generated by selecting problem features at random: e.g., the city grid
locations in the TSP. However, realworld problems generally exhibit some
form of structure, and it is unclear whether algorithms that perform well
on random instances will also perform well on more realistic, structured
instances. To date, relatively little research has considered structured
benchmarks for scheduling problems, despite the ubiquity of scheduling
in realworld problems. We ( JeanPaul
Watson , Laura Barbulescu
, L. Darrell Whitley
, and Adele E. Howe )
consider this issue in the context of the Permutation FlowShop Scheduling
Problem, or PFSP. Our paper, entitled Contrasting Structured and Random
Permutation FlowShop Scheduling Problems: SearchSpace Topology and Algorithm
Performance, is due to appear in the Spring 2002 issue of the INFORMS
Journal on Computing . Below, we provide links
to both the structured and random problem instances we analyze in our paper.
We also make available the code for our problem generator,
and document the various generator input parameters.
NOTE: the contents of this web page pretty much assume that you've read
the journal paper.
Benchmark Problems
Random Benchmark Problems
We analyze two types of random PFSPs. In the first type (rand),
the operation durations are independently and uniformly sampled from the
interval [1,99], following Taillard (1993) .
In the second type (randnarrrow), the operation durations are independently
and uniformly sampled from the interval [45,55]. The instances used in
our experiments are available via the following links:
20 x 20 rand
20x20 randnarrow
50 x 20 rand
50 x 20 randnarrow
100 x 20 rand
100 x 20 randnarrow
200 x 20 rand
200 x 20 randnarrow
Each link points to a g'zipped tar file containing 100 problem instances
and a file summarizing the lower bounds on the makespan and the best makespans
found by any of the algorithms we considered in our paper. The contents
of each archive are extracted to a subdirectory with an obvious name (e.g.,
2020rand). The subdirectory contains a 'summary' file that reports the
lower bounds/bestknown solutions, and a 'problems' subdirectory containing
the actual problem instances. The file format for the individual problem
instances is identical to the format introduced by Taillard
(1993) , and is the same format used in the PFSP benchmark suite available
from the OR Library .
Structured Benchmark Problems
We introduce and analyze three types of structured PFSPs: jobcorrelated,
machinecorrelated, and mixedcorrelated. The exact details of the generation
process are discussed in the paper. The instances used in our experiments
are available via the following links:
JobCorrelated
MachineCorrelated
MixedCorrelated
20 x 20
20 x 20
20 x 20
50 x 20
50 x 20
50 x 20
100 x 20
100 x 20
100 x 20
200 x 20
200 x 20
200 x 20
Each link points to a g'zipped tar file containing 100 instances for
each of the following values of a: 0.0, 0.1,
0.2, ..., 1.0. The contents of each archive are extracted to a subdirectory
with an obvious name (i.e., 2020jc). The subdirectory contains 11 subdirectories,
one for each value of a considered. The structure
of each a subdirectory is identical to that
reported for our random problem instances, as discussed above
.
Problem Generator
We have made available the problem instances used in our INFORMS Journal
on Computing paper to allow replication and further analysis of our results.
However, the goal of our research was specifically not to introduce
new PFSP benchmark problems. Rather, we are interested in analyzing search
space structure and algorithm performance on different types of problem
instances, in order to better understand the circumstances in which particular
algorithms are likely to perform well. To facilitate such research on the
PFSP, we have made the code for our problem generator publically available.
Download/Build
The code for our PFSP problem generator is available via the following
link: fspgen.tar.gz . The g'zipped tar file
contains contains 2 files: fspgen.cc and a makefile. The
code is written in standard C++, and makes use of the Standard Template
Library (STL). We have successfully built and tested the code on the following
platforms: HPUX (standard C++ compiler), Solaris 2.8 (GNU gcc 3.0 C++
compiler), and Linux (GNU gcc 3.0 C++ compiler). However, the code should
compile successfully on any platform with a reasonably modern C++ compiler
and an ANSIcompliant STL library. To build the generator, simply type
'make', which should produce an executable called fspgen. If you
have any problems building the generator code, or find any errors in either
our implementation or C++/STL compliance, please contact JeanPaul
Watson .
Generator Parameters
The commandline arguments to fspgen are as follows:
fspgen problemtype numjobs
nummachines random#seed [optionalarguments]*
The 'numjobs', 'nummachines', and 'random#seed' are selfexplanatory;
if a value of 0 is specified for the 'random#seed' parameter, the random
number generator is seeded using the value returned from the time
function required by the ANSI C standard. There are 5 valid values of the
'problemtype' parameters:

taillard

gaussian

jobcorrelated

machinecorrelated

mixedcorrelated
For all problem types, the operation durations are limited to the interval
[LB,UB]. By default, LB=1 and UB=99, following Taillard
. LB and UB can be overridden by specifying the optional arguments 'durationLB=X'
and 'durationUB=Y', respectively.
For the taillard problem type, the operation durations are independently
and uniformly sampled from the interval [LB,UB].
For the gaussian problem type, the operation durations are independently
and uniformly sampled from a normal distribution with mean ((UBLB)/2)+LB
and standard deviation (UBLB)/6. We did not analyze this type of PFSP
in our INFORMS Journal on Computing paper; it is considered in an
earlier paper ( Watson et al. 1999 ), where we
compare the search space structure of instances generated by sampling the
operation durations both uniformly and from a normal distribution.
The details of the generation process for the three correlated problem
types can be found in the paper. For each correlated problem type, lower
and upper bounds on the distribution halfwidths are central in the instance
generation process; the default values are 1 and 5, respectively, and can
be overridden by specifying the optional arguments 'distHalfWidthLB=X'
and 'distHalfWidthUB=Y', respectively. Similarly, the expected overlap
in the job/machine distributions is specified via the a
parameter; the default value is 0.5, and can be overridden by specifying
the optional argument 'alpha=Z'.
In the mixedcorrelated mode, there is an additional noise parameter,
which defaults to 0 and can be overridden by specifying the optional argument
'durationNoise=X'.
Output Format
All problem instances are output in a format identical to that used by
the PFSP benchmark suite available from the OR
Library . Following the specifications of the problem dimensions and
operations durations, we additionally output the following:

The lower bound on the optimal makespan of the problem instance, as defined
by Taillard (1993) .

The lower bound on the optimal makespan of the problem instance, as computed
via a transform to a proportionate flowshop (Pinedo
1995).

The minimum of the prior two lower bounds

The random number seed used to generate the problem instances
References.
Pinedo, M. 1995. Scheduling: Theory, Algorithms,
and Systems. Prentice Hall.
Taillard, E. 1993. Benchmarks for basic scheduling
problems. European Journal of Operational Research 64 278285.
Watson, JP., Barbulescu, L., Howe, A.E., and
Whitley, L.D. 1999. Algorithm performance and problem structure for flowshop
scheduling.
Appears in the Proceedings of the Sixteenth National Conference on Artificial
Intelligence (AAAI99).
Questions/Errors/Comments?
If you have any questions or comments regarding the contents of this web
page, please contact JeanPaul
Watson .
Web page last updated: January 15th, 2002.