Geoscience Reference
In-Depth Information
6. The grey pattern problem instances were suggested by Taillard (
1995
). It is
based on a rectangle of dimensions n
1
by n
2
. A grey pattern of m black points
is selected from the n
D
n
1
n
2
points in the rectangle while the rest of the
points remain white. This forms a “grey pattern” of density m=n. The objective
is to have a grey pattern where the black points are distributed as uniformly
as possible. This objective is achieved by defining a distance between pairs of
points according to some rule. The interaction matrix
f
c
ij
g
is the same as that of
the tightest cluster formulation because only distances between the m “black”
points are counted in the objective function. For more details see Taillard (
1995
)
and Drezner (
2006
).
7. The turbine balancing problem was suggested by Laporte and Mercure (
1988
).
Consider the manufacturing of a turbine engine, such as a hydro turbine or a
jet engine, with n blades. The blades are inserted into equally spaced slots. To
properly function, the turbine must be balanced. If all blades are identical, the
turbine engine is balanced. In reality, there are slight variations in the weights
of different blades, therefore the turbine is not perfectly balanced. Suppose that
the weights are designed to be 5 kg each and the variations across blades are
in the order of magnitude of milligrams. The problem is to find the “correct”
assignment of blades into slots so that the turbine will be as balanced as
possible. Let ı
i
be the deviation of blade i from the target weight. The objective
function is to find the permutation p.i/i
D
1;:::;nthat minimizes
(
n
)
2
C
(
n
)
2
ı
i
cos
2p.i/
n
ı
i
sin
2p.i/
n
X
X
:
iD1
iD1
Following
some
algebraic
manipulations
the
objective
is
equivalent
to
minimizing
n
X
ı
i
ı
j
sin
2
.p.i/
p.j//
n
:
i¤jD1
The weights are c
ij
D
ı
i
ı
j
and the distances are d
ij
D
sin
2
.i
j/
n
.The
weights can be either positive or negative.
8. The arrangement of Microarray layouts was suggested by de Carvalho Jr
and Rahmann (
2006
). The engineering component of this problem is quite
complicated. The production of commercial DNA microarrays is based on
a light-directed chemical synthesis driven by a set of masks or micromirror
arrays. Because of the natural properties of light and the ever shrinking feature
sizes, the arrangement of the probes on the chip and the order in which their
nucleotides are synthesized play an important role on the quality of the final
product. The reader is referred to de Carvalho Jr and Rahmann (
2006
)for
complete information.
