Keywords

1 Introduction

Flow shop is a shop floor configuration where all the jobs share the same sequence of processing. Every job has a deterministic span of time for completing its operation in each machine known as the processing time [1]. For processing a job, setup activities needed to be performed on each machine and the time incurred for doing these preparations is known as the setup time. Setup includes activities such as obtaining tools, cleaning the machines, setting the machines, fixing and removing jobs and returning tools. [2]. From the literature, it is observed that most studies in flow shops neglect the setup time or consider the setup time along with the processing time. However, in real-life situations, the presence of setup times cannot be neglected, especially in industries that manufacture paint, tiles, pharmaceuticals, automobiles, drugs and cosmetics, where the setup times are sequence dependent. In a sequence-dependent setup time (SDST) environment, the setup times of jobs depend on the current job to be processed and also on the previous job that has already been processed [3].

The studies on flow shops focus on optimising a single objective such as minimisation of makespan, total flow time, tardiness and number of setups [1, 3,4,5]. In real-life situations, a decision-maker has to deal with the optimisation of more than one objective. The presence of setup times and the attainment of multiple objectives increase the complexity of the scheduling problem. The solution to the multi-objective problem is obtained as a set of Pareto-optimal solutions or non-dominated solutions. A solution is said to be non-dominating, if it is not dominated by any other solutions of the multi-objective optimisation problem. Each solution in the Pareto-front has a better value for any one of the objectives and is a solution to the problem [6]. The decision-maker has to select a solution from the Pareto-front depending on the importance of the objective to be achieved. Researchers and practitioners adopt the weighted and non-weighted approach for solving the multi-objective problems. In a weighted approach, weights are attached to the objectives such that the multi-objective problem is converted to an equivalent single-objective problem. Hence, the present study focuses on the development of discrete particle swarm optimisation (DPSO) metaheuristic based on the weighted approach for solving the multi-objective SDST flow shop scheduling problem. The efficacy of the proposed metaheuristic is compared with the hybrid genetic algorithm.

The weighted approach has been adopted by many researchers like Rajendran and Zieglar [7], Eren and Guner [8], Eren [9] and Dhingra and Chandna [10] for solving the SDST flow shops with multiple objectives. Rajendran and Zieglar develop heuristics for scheduling an SDST flow shop with the objective of minimising weighted flow time and weighted tardiness. The researchers compare the performance of their heuristic with an existing heuristic, random search procedure and a greedy local search. The performance analysis reveals the better performance of the proposed heuristic. Eren and Guner address the scheduling problem in an SDST flow shop with the objective of minimising the weighted sum of total completion time and total tardiness. The authors develop an integer programming model for solving problems of up to 12 jobs. For solving larger-size problems, special heuristic algorithms and Tabu search are developed. The results from the computational studies indicate that the algorithms are effective for solving problems up to 1000 jobs. Eren considers the scheduling of a two-machine SDST flow shop with the objective of minimising four criteria. An integer programming model and Tabu search are developed for solving the multi-objective problem of up to 1000 jobs. Dhingra and Chandna develop a hybrid genetic algorithm minimising the weighted sum of total weighted squared tardiness and makespan of an SDST flow shop.

It is observed from the literature that the works related to SDST flow shops with multiple objectives are less in number. Further, no works have been reported with discrete particle swarm optimisation (DPSO) based on weighted approach for solving an SDST flow shop scheduling problem with multiple objectives. Thus, the objectives of the present study are as follows.

  • Development of a metaheuristic based on discrete particle approach for scheduling an SDST permutation flow shop with the objective of minimising makespan and mean tardiness.

  • Determination of the best set of parameters of the proposed metaheuristic.

  • Experimentation of the metaheuristic using benchmark problems.

  • Comparison of the proposed metaheuristic with a hybrid genetic algorithm.

The rest of the paper is organised as follows. The problem definition and the assumptions related to the study are presented in Sect. 21.2. Section 21.3 provides the detailed description of the proposed metaheuristic. Section 21.4 presents the method of determining the best set of parameters of the proposed metaheuristic. The experimentation details are described in Sect. 21.5. Section 21.6 presents the analysis of the results, and Sect. 21.7 provides the conclusion.

2 Problem Definition

The present study addresses the scheduling problem of an n job × m machine SDST flow shop with the objective of minimising makespan and mean tardiness. The assumptions made in the study are as follows.

  • All the jobs are available for processing at time zero.

  • The processing times of operations of jobs are known in advance.

  • Setup times for operations are considered explicitly from processing time and are sequence dependent.

  • Each machine can process only one job at a time.

  • No pre-emption is allowed.

  • The machines are continuously available, that is no breakdown of machines.

  • Notations

n :

Number of jobs to be scheduled

m :

Number of machines in the flow shop

p ji :

Processing time of job j on machine i

d j :

Due date of job j

C j :

Completion time of job j

s ijk :

Setup time on ith machine if job j is preceded by job k

σ :

Ordered set of jobs already scheduled, out of n jobs; partial sequence

q (σ, i):

Completion time of partial sequence σ on machine i (i.e. the release time of machine i after processing all jobs in partial sequence σ)

q (σj, i):

Completion time of job j on machine i, when the job is appended to partial sequence σ

f1 (x):

Makespan of sequence x

f2 (x):

Mean tardiness of sequence x

w 1 :

Weight assigned to makespan

w 2 :

Weight assigned to mean tardiness.

The objective function for an SDST flow shop scheduling problem is expressed as follows:

$${\text{Min}}\;f\left( x \right) = w_{1 } \times f_{1} \left( x \right) + w_{2 } \times f_{2} \left( x \right)$$
(21.1)

Since a sequence-dependent flow shop is considered, the recursive equation for the completion time of job j on machine i is determined using Eq. 21.2.

$$q\left( {\sigma_{j} ,i} \right) = \hbox{max} \left\{ {q\left( {\sigma ,i} \right) + s_{ijk} ,q\left( {\sigma_{j} ,i - 1} \right)} \right\} + p_{ji} ,$$
(21.2)

where job k precedes job j; q (σj, i) is the completion time of job j on machine i, when the job is appended to partial sequence σ; \(\left( {q\left( {\sigma ,i} \right) + s_{ijk} } \right)\) denotes the sum of the completion time of processing of job k on machine i and the setup time for job j on machine i; \(q\left( {\sigma_{j} ,i - 1} \right)\) is the completion time of the immediately preceding operation of job j on the previous machine; and pji is the processing time of job j on machine i.

The flow time of job j, Cj, is given by

$$C_{j} = q\left( {\sigma_{j} ,m} \right),$$
(21.3)

where \(q\left( {\sigma_{j} ,m} \right)\) is the completion time of the last operation of job j on machine m.

The makespan for a sequence of jobs is given by

$$f_{1} = \hbox{max} \left( {C_{j} ,\quad j = 1,2, \ldots ,n} \right)$$
(21.4)

The tardiness of a job is given by

$$t_{j} = \hbox{max} \left\{ {0,\left( {C_{j} - d_{j} } \right)} \right\}$$
(21.5)

The mean tardiness of a sequence of jobs is given by

$$f_{2} = \frac{{\mathop \sum \nolimits_{j = 1}^{n} t_{j} }}{n}$$
(21.6)

3 Discrete Particle Swarm Optimisation

Particle swarm optimisation (PSO) developed by Kennedy and Eberhart [11] for optimising continuous linear functions mimics the social behaviour of birds gathering their food. PSO optimises a problem by having a population of candidate solutions and moving these particles around in the search space over the particle’s position and velocity. The continuous PSO is not sufficient to solve the real-life problems with discrete problem features. Thus, the developers of PSO modified it to address the discrete problem, namely flow shop scheduling [12]. Discrete particle swarm optimisation (DPSO) is the discrete version of particle swarm optimisation. The difference between PSO and DPSO occurs in the representation of the solution. When PSO is applied for solving discrete optimisation problems (scheduling problems), the solution representation of PSO is modified to represent the discrete solutions [13]. In the present study, a variant of DPSO based on the weighted approach is developed for scheduling an SDST flow shop with the objective of minimising makespan and mean tardiness. The proposed metaheuristic is described in detail in Sect. 21.3.1.

3.1 The Proposed DPSO Metaheuristic

In DPSO, the initial population is considered as the swarm and each solution in the swarm is termed as the particle. The initial swarm for the present research is generated using the NEH heuristic [14] and the pair-wise interchange method. The generation of the initial swarm is followed by the computation of the objective function values of the particles in the swarm. Each particle in the swarm is represented as X1, X2, X3, …, XN, where N denotes the number of particles in the swarm. The personal best matrix corresponds to the objective function values of each particle in swarm. The objective function values are determined as the weighted sum of the objective function values. The lowest value among the personal best values is considered as the global best. Once the personal best matrix is formed, the position of the particles is updated. In PSO, every move of the particle to the next position is influenced by its own previous position, the position of the neighbouring particles and the particle in the leading position. The position of the particles is obtained from the velocity components. The position update is performed by two types of crossover and a mutation operation. The types of crossover involved are social crossover and cognition crossover. The previous position, the position of the neighbouring particles and the particle in the leading position are given by the mutation operation, the cognition velocity component and the social velocity component, respectively. The three components are determined using the following relations.

The position update equation consists of three components:

$$\lambda_{i}^{t} = w \otimes F_{1} (X_{i}^{t - 1} )$$
(21.7)
$$\delta_{i}^{t} = c_{1} \otimes F_{2 } (\lambda_{i}^{t} ,p_{i}^{t - 1} )$$
(21.8)
$$\mu_{i}^{t} = c_{2} \otimes F_{3} (\delta_{i}^{t} ,g_{i}^{t - 1} )$$
(21.9)

The first component given by Eq. 21.7 represents the velocity of the particle. In Eq. 21.7, F1 represents the mutation operator with a probability of w. A uniform random number r is generated between 0 and 1. If r is less than w, then the mutation operator is applied to generate a perturbed permutation of the particle, otherwise the particle is kept without any change. The second component obtained using Eq. 21.8 represents the cognition part of the particle. F2 in Eq. 21.8 represents the cognition crossover operator with a crossover probability c1. Here, \(\lambda_{i}^{t}\) and \(p_{i}^{t - 1}\) are the two parents for crossover where \(\lambda_{i}^{t}\) is the particle obtained from mutation and \(p_{i}^{t - 1}\) is the particle in the personal best matrix. The occurrence of this crossover operation depends on the random number generated. The third or social component is provided by Eq. 21.9 where F3 and c2 represent the crossover operator and social crossover probability, respectively. The parents for crossover are \(\delta_{i}^{t}\) and \(g_{i}^{t - 1}\) where \(\delta_{i}^{t}\) is the particle obtained from the cognition crossover and \(g_{i}^{t - 1}\) is the global best solution. The crossover operation depends on the random number generated. The objective function values of the velocity components are determined. Since the problem is of minimisation type, the least value among the three components is considered and the position is updated. A local search is performed on these solutions, which increases the diversity of the solutions. A non-dominant sorting procedure is applied to the solutions obtained from the local search, and the set of non-dominated solutions are updated in each generation. The solutions obtained from the local search become the swarm for the next generation. The procedure is repeated until it reaches the specified termination criteria.

3.2 Hybrid Genetic Algorithm

The hybrid genetic algorithm (HGA) is developed by combining the evolutionary method of genetic algorithm with a local search method. The initial population is generated using NEH and the pair-wise interchange method. The population is then subjected to genetic operators of selection, crossover and mutation. A local search is applied to the solutions obtained from mutation. The set of Pareto-optimal solutions is obtained by applying the non-dominant sorting algorithm to the offspring of mutation. The procedure is repeated for a specified number of generations. The hybrid GA is applied to the benchmark problems with the best set of parameters obtained from Taguchi’s robust design and the utility index concept.

4 Parameter Configuration of DPSO

The parameters of the proposed DPSO include type of mutation, probability of mutation, type of cognition crossover, probability of cognition crossover, type of social crossover, probability of social crossover and the swarm size. The parameters of the DPSO metaheuristic are determined using Taguchi’s robust design in combination with the concept of utility index [15, 16]. The parameters and their different levels are shown in Table 21.1. The L18 orthogonal array is selected, and the objective function values are determined for each trial. Once the objective function values are computed, the average response value of each objective function for each factor level is determined. The average values of the objectives for each factor level are presented in Table 21.2. The average response value corresponding to each level of the parameters is computed from the objective function values and is shown in Table 21.3.

Table 21.1 Parameters and their levels
Full size table
Table 21.2 Average response value by factor levels
Full size table
Table 21.3 Average objective value corresponding to each level
Full size table

The preference number for each objective function is obtained using Eq. 21.10.

$$P_{b} = Z\log \frac{{y_{b} }}{{y_{b}^{{\prime }} }},$$
(21.10)

where \(y_{b}\) is the value of the objective b, \(y_{b}^{\prime}\) is the maximum or minimum acceptable value of the objective and Z is a constant. The value of Z has to be determined for computing the preference number for each objective. It is assumed that at optimum, value of the objective \(P_{b} = 9\), and hence, the value of Z is computed as follows.

$${\text{At}}\;{\text{optimum}},y_{b}^{{\prime }} {\text{of}}\;{\text{objective}}\;b,P_{b} = 9;\;Z = \frac{9}{{\log \frac{{y_{b}^{ *} }}{{y_{b}^{{\prime }} }}}},$$
(21.11)

where \(y_{b}^{*}\) is the predicted optimal value of attribute b.

The predicted optimal value of makespan = 1651.87 + 1645. 39 + 1643.81 + 1638.61 + 1645.72 + 1640.81 + 1642.64 − 3 × 1655.48 = 6838.3.

The predicted optimal value of mean tardiness = 295.85 + 293.64 + 293.43 + 251.64 + 295.19 + 253.50 + 293.38 − 3 × 292.88 = 1098.

The preference number is determined for makespan and mean tardiness from the predicted optimal values using Eq. 21.10. The utility index is computed using Eq. 21.12.

$$U_{d } = \mathop \sum \limits_{b = 1}^{l} a_{b} P_{b} ,$$
(21.12)

where ab is the weight assigned to the objective b, Pb denotes the preference number of objective b, l is the number of objectives and d is the experiment number. The preference number and the utility index corresponding to each experiment of the orthogonal array are shown in Table 21.4. The average utility index corresponding to each level of parameters is determined and is provided in Table 21.5. From Table 21.5, it is observed that parameter B, that is the mutation probability, has the highest range, and hence, it is the influencing factor on the performance characteristics of the algorithm. The order of importance of the parameters on the performance of the algorithm can be listed as follows: mutation probability, probability of social crossover, type of social crossover, type of cognition crossover, swarm size, probability of cognition crossover and type of mutation. The different levels of parameters are plotted with the average utility index, and the parameter with the highest utility value is selected as the best parameter. The utility index value for each parameter at different levels is shown in Fig. 21.1. The parameter values with the highest utility values are A1 B3 C2 D3 E3 F1 G2.

Table 21.4 Preference number and utility index
Full size table
Table 21.5 Average utility value for each level of parameters
Full size table
Fig. 21.1
figure 1

Utility index value for each parameter at various levels

Full size image

The best set of parameters of the proposed DPSO is obtained from Taguchi’s method, and the concept of utility value is shown in Table 21.6.

Table 21.6 Best set of parameters of DPSO
Full size table

5 Experimentation

Experimentation of the proposed DPSO is carried out on the SDST benchmark problems of flow shop scheduling. The study is conducted on 20 jobs, 50 jobs and 100 jobs with the machine size as 5, 10 and 20. The method for generating the setup times and the due dates required for the study are provided in the following subsection. The algorithms are applied with the best set of parameters determined using Taguchi’s orthogonal array and utility index as described in the preceding section. The DPSO metaheuristic terminates after examining 1000 solutions for 20 jobs and 50 jobs, whereas the termination occurs after examining 1500 solutions for 100 jobs. All the problem instances are solved using MATLAB software on a desktop computer that runs on an Intel Core Processor with 3 GHz RAM.

5.1 Data Generation for the Problems for Computational Studies

In the present study, the setup times of jobs are considered explicitly. Hence, the setup times of jobs are generated using the setup time level concept. The setup time level is expressed as the ratio of maximum setup time to the maximum processing time. The setup time for the jobs is expressed using the following relation.

$$\begin{aligned} & {\text{Setup time level}} = \frac{{\hbox{max} \;s_{ijk } }}{{\hbox{max} \;p_{ijk} }} \times 100 \\ & \quad {\text{for all }}i = 1,2, \ldots ,m;\;\;j = 1,2, \ldots ,n;\;\;k = 1,2, \ldots ,n , \\ \end{aligned}$$
(21.13)

where pijk is the maximum time element of the processing time matrix and sijk is the maximum time element of the setup time matrix. The setup time level is assumed to be 25%, and hence, the setup time of jobs is generated in a uniform distribution in the interval between 1 and 25. The processing times are obtained from the benchmark problems of flow shop scheduling [17]. The due dates of jobs required for the study are generated using the method of total work content. The due date of a job is expressed as follows.

$$\begin{aligned} {\text{Due date of a job}} & = {\text{arrival time}} + r \\ & \quad \times \left( {{\text{processing time of the job}} + {\text{setup time of the job}}} \right) , \\ \end{aligned}$$
(21.14)

where r is the allowance factor and it is set equal to 2.

$$\begin{aligned} & {\text{Setup time of a job}} \\ & \quad = {\text{number of operations of the job}} \times {\text{average setup time of an operation}} \\ \end{aligned}$$
(21.15)

6 Results and Discussion

The Pareto-optimal solutions are determined for the nine problem sizes using the DPSO metaheuristic. The efficacy of the proposed metaheuristic is compared with the hybrid genetic algorithm based on the performance measures such as mean ideal distance (MID), computational time, diversification matrix (DM), average objective values and minimum objective values. The obtained Pareto-optimal solutions for the nine SDST benchmark problem sizes are shown in Table 21.7. It is observed from the values in Table 21.7 that for most of the problem sizes, the values of makespan and mean tardiness obtained from DPSO are better than the hybrid genetic algorithm. In the 20 job × 20 machine problem, both the metaheuristics provide mean tardiness values as zero for one of the solutions in the Pareto-optimal set. However, a better makespan value is obtained from DPSO for the zero mean tardiness value.

Table 21.7 MID, computational time and the diversification matrix for the SDST benchmark problems
Full size table

6.1 Performance Analysis of the Proposed Metaheuristic Based on the Mean Ideal Distance, Computational Time and the Diversification Matrix

The MID values, computational time and DM values of the proposed metaheuristic are shown in Table 21.8. From Table 21.8, it is observed that for all the problem sizes except the 20 job × 5 machine problem instance, the MID values are lower for the DPSO metaheuristic. Lower MID values indicate better performance of the metaheuristic. Hence, it is evident from the MID values that the DPSO metaheuristic performs better than the hybrid genetic algorithm. When the computational time is considered, the time taken for the DPSO metaheuristic to provide the Pareto-optimal solutions is lower for most of the problem sizes when compared to the hybrid genetic algorithm. The DM values also reveal the superior performance of DPSO metaheuristic to hybrid genetic algorithm. The higher values of DM indicate the better performance of the metaheuristic. Thus, in terms of MID values, computational time and DM values, the DPSO metaheuristic outperforms the hybrid genetic algorithm.

Table 21.8 Minimum and average makespan values for the SDST benchmark problems
Full size table

6.2 Performance Analysis Based on the Average and Minimum Objective Function Values

The average values and the minimum values of makespan and mean tardiness obtained for the proposed algorithms are shown in Tables 21.9 and 21.10, respectively. From Table 21.10, it is observed that the minimum value of makespan is obtained from the DPSO metaheuristic for all the problem instances. Further, the average makespan provided by the DPSO metaheuristic has lower values for all the problem sizes except the 20 job × 5 machine problem. In that problem instance, though the average makespan value is better for HGA, the minimum makespan is provided by the DPSO metaheuristic. Similarly, the minimum and average values of mean tardiness have better values for the DPSO metaheuristic except the 20 job × 5 machine case. Hence, it is evident from the results that the DPSO metaheuristic performs better when compared to the hybrid genetic algorithm.

Table 21.9 Minimum and average mean tardiness values for the SDST benchmark problems
Full size table
Table 21.10 Pareto-optimal solutions for the SDST benchmark problems
Full size table

7 Conclusions

The present study proposes a DPSO for solving the bi-objective scheduling problem of an SDST flow shop. Computational studies using the SDST benchmark problems reveal that on an average, the proposed DPSO provides an improvement of 7.8, 22.3 and 11.3% when compared with HGA for the measures such as MID values, computational time and diversification matrix, respectively. In the present study, continuous availability of the machines is assumed. However, in real-life situations, we may encounter breakdown and repair of machines. Thus, the work can be extended by integrating appropriate scheduling and maintenance policies. Other methods for generating the initial population and due dates can be examined. Performance measures other than makespan and mean tardiness can also be considered.