Forward Backward Transformation - Differential Evolution: A Topic for Global Permutation-Based Combinatorial Optimization - page 59

P 1 , j n

P 1 , j 1 P 1 , j 2

P 2 , j 1

P i , j k

P i , j k +1

P i +1 , j k +1

P i +1 , j k

P m , j 1 P m , j n

Fig. 3.10. Directed graph representation for the makespan

n
j =1 c ij , while the
condition for tardiness is c m , j > d j . The constraint of Equation 3.9 applies to these two
problem descriptions.

m
∑
i =1

machine i . For a given sequence, the mean flow time, MFT = n

3.6.1 Flow Shop Scheduling Example

Generally, two versions of flowshop problems exist. Finding an optimal solution when
the sequence changes within the schedule are flexible and changes allowed are generally
harder to formulate and calculate. The schedules which are fixed are simpler to calculate
and are known as permutative flow shops.
A simple representation of flowshop is given through the directed graph method .The
critical path in the directed graph gives the makespan for the current schedule. For a
given sequence j 1 ,.., j n , the graph is constructed as follows: For each operation of a
specific job j k on a specific machine i , there is a node ( i , j k ) with the processing time
for that job on that machine. Node ( i , j k ), i = 1 ,..., m 1,hasarcs

going to nodes ( i + 1 , j k ) and ( i , j k +1 ). Nodes corresponding to machine m have only
one outgoing arc, as do the nodes in job j n . Node ( m , j n ), has no outgoing arcs as it
is the terminating node and the total weight of the path from first to last node is the
makespan for that particular schedule [30]. A schmetic is given in Fig 3.10.
Assume a representation of five jobs on four machines given in Table 3.26.
Given a schedule

− 1and k = 1 ,...., n −

{ 1 , 2 , 3 , 4 , 5 } which is the schedule { j 1 , j 2 , j 3 , j 4 , j 5 } , implying that

all jobs in that sequence will transverse all the machines.