Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times

Abstract

Industries such as textiles, paints, chemicals, paper, drugs and pharmaceuticals operate as flow shops with sequence-dependent setup times (SDST). The sequence-dependent setup environment is characterised by the dependence of the setup time on the current job and also on the previous job processed on that machine. To further complicate the problem, in most real-life scenarios, decision-makers have to optimise more than one performance measure while scheduling jobs on machines. This work considers such a multi-objective SDST flow shop environment. The objectives considered in the present study are minimisation of makespan and minimisation of mean tardiness. Four metaheuristics, viz. non-dominated sorting genetic algorithm (NSGA) II, hybrid NSGA II, discrete particle swarm optimisation and hybrid discrete particle swarm optimisation, belonging to the category of intelligent optimisation techniques, are developed to obtain a set of Pareto-optimal solutions. The proposed metaheuristics are applied on benchmark SDST flow shop problems and their performance compared using different measures. Analysis of the results reveals that hybrid NSGA II outperforms the other three algorithms for all problem sizes considered in the present research. The results also indicate that hybridisation of the metaheuristics with variable neighbourhood search improves their performance.

Appendices

Appendix: Illustration of the Algorithms

A numerical illustration of the algorithms proposed in the present work is described in this section. For the purpose of illustration, a flow shop with seven jobs and three machines is considered, with the objective of minimising makespan and minimising mean tardiness. The processing time and due date of the jobs are presented in Table 13.

Table 13 Processing time and due date of the jobs

The setup times of the three machines are given in Tables 14, 15 and 16, respectively.

Table 14 Setup time for machine 1

Table 15 Setup time for machine 2

Table 16 Setup time for machine 3

The algorithms are illustrated in the following sections.

Appendix 1: Illustration of NSGA II

The initial population N for the algorithm is assumed as 10 (for illustration). The initial population along with their objective function values are presented in Table 17.

Table 17 Objective function values of initial population

Non-dominated sorting is performed on the initial population, and the different non-dominated fronts obtained are presented in Table 18.

Table 18 Non-dominated sorting

The parents for crossover are selected using the binary tournament selection operator based on the ranks obtained from the non-dominated sorting. The mating pool for crossover is presented in Table 19.

Table 19 Mating pool of parents for crossover

Single-point crossover with a crossover probability of 0.9 is applied on the strings in the mating pool. The offsprings obtained from the crossover operation are presented in Table 20.

Table 20 Offsprings after crossover operation

The offsprings from the crossover operation are subjected to mutation with a specific mutation probability. The method of swap mutation is adopted in the present work, and the offsprings from mutation are presented in Table 21.

Table 21 Offsprings after mutation operation

The offsprings from the mutation operation are combined with the initial population to form the new population of size 2N. The new population is sorted into different non-dominant fronts using the non-dominated sorting procedure. The new initial population of size N is to be formed from a population of size 2N. Since all the solutions in the 2N population cannot be accommodated in the new initial population, the crowding distance operator (Sect. 4.1.2) is used to select the required solutions for the new initial population. Once the new population is formed, the non-dominant solution set is updated. Table 22 presented the new population for the second generation.

Table 22 Population for the second generation

The procedure is repeated for a pre-specified number of generations. The solutions belonging to the first front become the Pareto-optimal solutions, i.e. the sequences 1–3–2–4–5–7–6 and 5–2–7–6–4–3–1.

Appendix 2: Illustration of Variable Neighbourhood Search

Consider a sequence 3–5–7–1–2–6–4–7 with seven jobs. The makespan value and the mean tardiness value of the sequence are 74 and 7.14, respectively. VNS is applied on the sequence. The various neighbourhood structures involved are swap, reversion and insertion. The sequence is first subjected to swap operation. The objective function values obtained after the first swap operation are 73 and 10.29. Since the makespan value is minimum compared with the initial solution, the solution is accepted and VNS is continued with swap operation. The swap operation is continued until there is no improvement in both the objective function values. Then, the swap operation is followed by reversion operation. Reversion is applied on the solution, and since the objective function values have no improvement with reversion, the next neighbourhood structure of insertion is applied. The objective function values have no improvement with insertion neighbourhood also. The final sequence after the VNS operation is 7–5–6–1–3–4–2, with makespan and mean tardiness values of 67 and 4.57, respectively. Table 23 presented the various neighbourhood structures applied to the solution and the improvement in the objective function values.

Table 23 Variable neighbourhood search

Appendix 3: Illustration of DPSO algorithm

The swarm size is assumed as 10 (for illustration). The sequences which form the initial population along with their objective function values are presented in Table 24.

Table 24 Objective function values of initial population

The non-dominated sorting procedure is performed on the population, and the solutions belonging to the first non-dominated front form the initial Pareto-optimal set. These solutions are considered as the global best solutions. Table 25 provides the global best solutions obtained.

Table 25 Global best solutions

The velocity components of each particle in the swarm are determined from mutation, cognition crossover and social crossover. The procedure for determining the velocity components of the first particle in the swarm is illustrated below. Consider the first particle in the swarm, i.e. 1–3–5–7–4–6–2 (Table 26).

Table 26 Global best solutions

The position of the particle is updated by selecting the best velocity component among the three components. Similarly, the velocity components of the other particles are determined, and their positions are updated. The updated position of particles in the swarm is presented in Table 27.

Table 27 Particles with their updated position

The updated solutions are added to the Pareto-optimal set, and the Pareto-optimal set is then sorted using the non-dominated sorting procedure. The Pareto-optimal solution after the first iteration is obtained as 6–5–3–2–7–4–1, with makespan value of 64 and mean tardiness 1.86. Thus, the Pareto-optimal set is updated. The solutions in the Pareto-optimal set become the global best solutions for the next generation. The solutions in the population with the updated positions become the initial population for the next generation. The algorithm terminates after a pre-specified number of generations.