1 Introduction

A flow shop is characterised by a unidirectional flow of work with a variety of jobs being processed sequentially in a one-pass manner. In many manufacturing and assembly facilities a number of operations needs to be done on every job. A “job” is thus a collection of operations to be performed on an item or unit with applicable technological constrains. This implies that all jobs have to follow the same route, even if the jobs are identical. The machines are set up in a series and such a processing environment is referred to as a flowshop.

Shop schedules are generally evaluated by aggregate quantities that involve information about all jobs, resulting in a one-dimensional performance measure usually expressed as a function of the set of job completion or processing times. A performance measure frequently used to compare the quality of two schedules is a makespan, the total time required to process all the jobs. Other common measures include the mean flow time and the job tardiness. Although the different performance measures are often correlated, one can construct an example for which a schedule may be good according to one measure, but which may perform poorly on others. In this paper, it has been considered desirable to investigate the optimal sequence, which minimises the makespan for the flow shop scheduling (FSS). A heuristic algorithm namely, the ant system (AS) is employed to minimise the objective function namely the makespan. Further, its output is given to an evolutionary technique, namely a genetic algorithm (GA) to optimise the main criteria.

2 The literature survey

Janiak in his work [1] addresses the problem where some of the job operations’ processing times are a convex decreasing function of the amounts of resources allocated with the objective of minimising the makespan.

Leslie A.Hall work [2] involves a polynomial approximation scheme for a two-machine flow shop scheduling problem with the additional constraint that each job has a release date, when it first becomes available for processing.

Celia A. Glass, Chris N. Potts and Vitaly A. Strusevich in their work [3] deal with batching of operations of jobs—a key issue in machine scheduling. The objective is to minimise makespan and processing time of a batch on a machine.

Okamoto Shusuke, Watanabe Chie and Iizuka Hajime presented a parallel algorithm for solving n-job, m-machine flow shop problems [4] based on the parallelisation of the branch and bound method along with all search methods to minimise the processing time.

Mohamed Haouari and Thouraya Daouas proposed [5] an exact branch and bound method based on a recursive enumeration of potential inputs and outputs of machines for three-machine assembly type flow shop problem.

Victor Portugal and J. L. Scott in their work [6] address the problem of FSS with the objective of minimising the makespan and the maximum tardiness. Thomas Stutzle and Hoos applied the MAX-MIN ant system [7], one of the most efficient ant colony optimisation algorithm to the traveling salesman problem.

Riad Aggoune’s work [8] deals with the scheduling of flow shop with the availability constraints (FSPAC) where two pre-emptive FSPAC with arbitrary number of machines and arbitrary number of unavailability periods on each of them are considered. A GA and tabu search are used to attain the objective.

An evolutionary search approach, a GA for job shop scheduling problems is given by Kobayashi, Ono and Yamamura [9]. K.J. Shaw and P.J. Fleming’s paper [10] reports that applying a GA to scheduling problems is a powerful technique which has the potential to be used as a multi-objective optimisation tool in production manufacturing applications.

S. Chen and S. Smith [11] considered the precedence constraints for the search space to minimise tardiness and earliness cost. Johann Hurink and Sigrid Knust [12] deal with flow shop problems involving transportation times where all transportations are done by a single robot.

From the literature survey undergone, the most important criteria in flow shop scheduling is found to be the minimisation of makespan. It can also be seen that not much concentration has been given on the hybridization of heuristics. Therefore, in this paper, an attempt has been made to hybridise the AS and the GA for the flow shop problem with the minimum makespan as objective.

3 Problem statement

The objective of the problem is to minimise the makespan. The problem is defined as follows:

a):

Given the processing time (time matrix) of ‘n’ jobs on ‘m’ machines, first the best sequence of the jobs is determined according to the probability function which comprises of

  • Intensity of trial

  • Evaporation of trial

  • Visibility

using the heuristic AS algorithm.

b):

This optimum job sequence is given as input to an evolutionary search technique, namely; a GA due to which the more optimal sequence is generated.

4 The AS

An AS is a new general purpose heuristic, which can be used to solve different combinatorial problems. Given a set of machines, jobs and processing time of job ‘i’ on machine ‘j’ (t ij ), flow shop scheduling can be stated as the problem of finding the minimal processing time such that all the jobs are processed in all the machines.

Here the number of ants are taken as equal to the number of the jobs at time ‘t’.

The algorithm [13] is stated as follows:

1

Initialise

Set: t=0 (t is the time counter)

Set: NC=0 (NC is the cycles counter)

For every successive jobs (i,j) set an initial value τ ij (t)= c for trial intensity and Δι ij =0

Place the m ants on the n nodes.

2

Set s:=1 (s is the tabulist index)

For k:=1 to m do

Place the starting job of the kth ant in tabu k (s)

3

Repeat until the tabulist is full (this step will be repeated (n–1) times)

Set s:=s+1

For k:=1 to m do

Choose the job ‘j’ to be processed, with probability p k ij (t)

$$p^{k} _{{ij}} {\left( t \right)} = {\left[ {\tau _{{ij}} {\left( t \right)}} \right]}{\left[ {\eta _{{ij}} } \right]}/\sum {\left[ {\tau _{{ik}} {\left( t \right)}} \right]}{\left[ {\eta _{{ik}} } \right]}\;{\text{if}}\;j \in \;allowed_{k} $$

k∈allowed k

where η ij —visibility

4

For k: = 1 to m do

Compute the processing time L k of the tour described by the kth ant

Update the shortest processing time found.

For any successive jobs (i,j)

For k: = 1 to m do

$$ \Delta l^{k}_{{ij}} = \left\{ {\begin{array}{*{20}l} {{Q \mathord{\left/ {\vphantom {Q {L_{k} \;{\text{if the kth ant uses successive jobs}}}}} \right. \kern-\nulldelimiterspace} {L_{k} \;{\text{if the kth ant uses successive jobs}}}\;{\left( {i,j} \right)}\;{\text{in its tour}}} \hfill} \\ {{{\text{0}}{\text{,}}\;{\text{otherwise}}} \hfill} \\ \end{array} } \right. $$

where Δι k ij —quantity per unit length of trial substance.

$$ \Delta \iota _{{ij}} = \Delta \iota _{{ij}} + \Delta \iota ^{k} _{{ij}} $$

5

For every successive jobs (i,j) compute ι ij (t+n) according to the equation

$$\iota _{{ij}} {\left( {t + n} \right)} = \rho \iota _{{ij}} {\left( t \right)} + \Delta \iota _{{ij}} $$

Set t:=t+n

Set NC:=NC+1

For every successive job (i,j) set Δι ij =0

6

If (NC<NC max ) and (not stagnation behaviour)

Then

Empty all the tabulists

Go to step 2

Else

Print shortest sequence

Stop

5 GAs

GAs mimic the principles of natural genetics and natural selection to constitute search and optimisation procedures. GAs differing from conventional search techniques start with an initial set of random solutions called population. Each individual in the population is called a chromosome (a string of symbols), representing a solution to the problem at hand. The chromosomes evolve through successive iterations, called generations. During each generation, the chromosomes are evaluated using some measures of fitness. To create the next generation, new chromosomes called offspring, are formed by

(a):

Merging two chromosomes from current generation using a crossover operator or

(b):

Modifying a chromosome using a mutation operator

Formation of new generation involves (a) selecting some of the parents and offspring according to the fitness values and (b) rejecting others so as to keep the population size constant. After several generations, the algorithm converges to the best chromosome.

The steps involved in GAs [14] are as follows:

Step 1::

choose a coding to represent problem parameters, a selection operator, a crossover operator, and a mutation operator. Choose the population size, n, crossover probability P c and mutation probability P m . Initialise a random population of strings of size L. Choose a maximum allowable generation number t max . Set t=0.

Step 2::

evaluate each string in the representation.

Step 3::

if t>t max or any other termination criteria is satisfied, terminate.

Step 4::

perform reproduction on the population.

Step 5::

perform crossover on random pairs of strings.

Step 6::

perform mutation on every string.

Step 7::

evaluate strings in the new population. Set t=t+1 and go to step 3.

6 An illustrative example of the AS

To illustrate the flow shop scheduling, let there be 10 jobs to be processed on 10 machines. The time matrix (i.e., the processing time of 10 jobs on 10 machines) is given in Table 1. In the AS, the sequences equivalent to the number of jobs are generated. The AS can therefore process the 10 jobs on 10 machines in any of the 10 possible combinations as shown in Table 2 (first iteration).

Table 1 The processing time for jobs in machines
Full size table
Table 2 The sequence of jobs after the first iteration in the ant system
Full size table

After several iterations, the optimal sequence is

$$J_{3} \;J_{4} \;J_{2} \;J_{{10}} \;J_{1} \;J_{9} \;J_{7} \;J_{6} \;J_{8} \;J_{5} $$

The makespan for the above sequence is 281.

7 An illustrative example of a GA

In a GA, the input is given as random as shown in Table 3 and the parents for the crossover and mutation are selected based on the respective probabilities.

Table 3 The random input to the genetic algorithm
Full size table

This procedure is repeated for several iterations and the optimal sequence with the minimum makespan is found to be

$$J_{8} \;J_{5} \;J_{6} \;J_{{10}} \;J_{3} \;J_{1} \;J_{4} \;J_{2} \;J_{7} \;J_{9} \;{\text{with}}\;{\text{makespan}}\;261.$$

8 An integration of the AS and a GA

On giving the output of the AS as an input to the evolutionary search technique-GA, the optimal sequence is obtained.

The optimal sequence is J 10 J 8 J 6 J 5 J 3 J 9 J 4 J 7 J 2 J 1 with makespan 259.

The hybrid technique is evaluated for a large number of flow shop problems of varying sizes i.e., 360 problems in total with jobs varying from 5 to 30 and machines varying from 5 to 30 in steps of 5.

It has been observed from Table 4 that the hybridisation of metaheuristics has given better results than the pure metaheuristics. A hybrid has given best minimum makespan for 71.11% of time whereas the AS for 6.67% of the time and genetic algorithm for 49.44% of time as shown in Fig 1.

Table 4 A comparison of results
Full size table
Fig. 1
figure 1

The best minimum makespan

Full size image

9 Conclusions

This paper has focused on minimising the makespan for the flow shop scheduling problem. These problems are modelled first; subsequently solution schemes are chosen and then analysed in detail. In this context, the AS and the evolutionary search technique called a GA are approached separately towards the objective and then compared with the hybrid of both these techniques. The heuristic approach presented in this paper is not limited to the specific scenario and can be extended to the general ‘n’ jobs and the ‘m’ machines case.

The hybrid approach has been shown to be more productive than the pure heuristic methods to combinatorial problems. The approach can also be extended to the objectives such as minimising the tardiness, meeting due dates, maximising the machine utilisation, minimising time lags, etc. Similar hybrids can be formed from various heuristics for meeting the objectives.