Introduction

The idea of the parallel bat algorithm (BA) is to divide the artificial bats into independent subpopulations so that they can share the computation load. The parallel processing also had been applied for the existing methods, including in the ant colony system with communication strategies (Chu et al. 2004), a parallel particle swarm optimization algorithm with communication strategies (Chu et al. 2005), parallel cat swarm optimization (Tsai et al. 2008), the island-model genetic algorithm (Whitley et al. 1998), and parallel genetic algorithm (Abramson and Abela 1991). The global search capacity could be extended and the accuracy could be increased from the parallelized subpopulation structure of artificial agents more than that the original structure. The parallelized strategies simply share the computation load over several processors. The sum of the computation time for all processors can be reduced compared with the single processor works on the same optimum problem (Kuck 1977). Besides, the no free lunch theorem (Wolpert and Macready 1997) has logically proven that there is no meta-heuristic algorithm best suitable for solving all optimization problems. In other words, a particular meta-heuristic algorithm may show highly promising results on a set of problems, but the same algorithm may show poor performance on a different set of problems (Wolpert and Macready 2005). This theorem makes the field of meta-heuristic algorithm and the study of its applications highly active. This also motivates us to consider the strength of the algorithm in parallel processing for solving complicated and difficult scheduling problems (Garey and Johnson 1990).

Scheduling can be defined as a problem of finding an optimal sequence to execute a finite set of operations of satisfied constraints (Błażewicz et al. 1996). It is a decision-making process of allocating resources over time to perform a collection of required tasks. Effective scheduling plays a vital role in the growth of any kind of industries. Different types of scheduling problems were addressed in the literature with unlike performance measures (Behnamian and Fatemi Ghomi 2014; Gen and Lin 2014). Single machine scheduling (Çakar 2011), flow shop scheduling (Mirabi et al. 2013), parallel machine scheduling (Ying et al. 2012), job shop scheduling (Meeran and Morshed 2012) are some of the important types of scheduling environments. Among them, the job shop scheduling problem (JSSP) is considered in this paper. Minimization of makespan, total of flow time, mean of flow time, total earliness, total tardiness, weighted earliness, and tardiness and number of tardy jobs are the important objective functions of scheduling problems. The objective of this paper is to minimize makespan. In recent years, an interest in using meta-heuristic methods to solve JSSP has been growing rapidly, such as simulated annealing (SA; Laarhoven et al. 1992; Song et al. 2012), tabu search (TS; Dell’Amico and Trubian 1993; Geyik and Cedimoglu 2004; Zhang et al. 2007), genetic algorithms (GA; Davis 1985; Moin et al. 2015; Gonçalves et al. 2005; Cheng et al. 1996), particle swarm optimization (PSO; Lian et al. 2006; Lin et al. 2010), artificial immune system and their hybrids (AIS; Coello et al. 2003; Qiu and Lau 2014; Luh and Chueh 2009; Zhang and Wu 2010), discrete artificial bee colony (DABC; Yin et al. 2011), discrete imperialist competitive algorithm (Hosseini and Al Khaled 2014) and hybrid imperialist competitive algorithm(Hosseini et al. 2014). These approaches comprise the emergence of promise for conquering the combinatorial exploration in a variety of decision-making arenas.

A new meta-heuristic optimization algorithm, namely, BA and its parallel version based on swarm intelligence and the inspiration for observing the searching for the prey of the bats was introduced as in (Yang 2010; Tsai et al. 2014). The key advantage of the BA is that it can provide very quick convergence at a very initial stage by switching from exploration to exploitation (Yang and He 2013). It is potentially more powerful than PSO and GA as well as harmony search. The primary reason is that BA uses a good combination of major advantages of these algorithms in some way. Moreover, PSO and harmony search are the special cases of the BA under appropriate simplifications.

In this paper, the concept of a parallel processing is applied to BA and a communication strategy for PBA is proposed to solve JSSP. A set of independent jobs must be processed on a set of available machines in JSSP. Each job is a sequence of operations. Each operation requires a predefined machine. These are all handled efficiently with PBA.

The rest of this paper is organized as follows. The problem of job shop scheduling is reviewed in “The job shop scheduling problem” section. The analysis and designs for PBA with the communication strategy and its experimental results are presented in “Parallelized bat algorithm with a communication strategy” section. The application of PBA to the JSSP problems is presented in “Parallel bat algorithm for JSSP” section. “Experimental results” section shows further results of testing JSSP. Finally, the conclusion is summarized in “Conclusion” section.

The job shop scheduling problem

The JSSP was defined (Cheng et al. 1996; Gonçalves et al. 2005) as follows. There are a machine set \(\hbox {M} = \{\hbox {M}_{1}, \hbox {M}_{2}, {\ldots }, \hbox {M}_{\mathrm{m}}\}\) and a job set \(\hbox {J}=\{\hbox {J}_{1}, \hbox {J}_{2}, {\ldots }, \hbox {J}_{\mathrm{n}}\}\). Each job, \(\hbox {J}_{\mathrm{k}}\), must go through m machines to complete its work. One job consists of a set of operations, and the operation order for the machines is predetermined. Each operation uses one of the m machines to complete one job’s work for a fixed time interval. Once an operation is processed on a given machine, it cannot be interrupted before it finishes the procedure. The sequence of the operations of a job should be predefined and maybe different for any job. Every job has a sequence of m operations. Each machine can process only one operation during the time interval. A schedule is the assignment of operations to time slots on a machine. The objective of the JSSP is to find an appropriate schedule. A good schedule is an appropriate operation permutation for all jobs that can minimize the makespan or one that minimizes the idle time of machines. The makespan is denoted as \(C_{max}\). It is the maximum total completion time of the final operation in the schedule of \(n\times m\) operations. A set of the operations is denoted as \(\hbox {O} =\{0, 1, 2,\ldots ,n\times m+1\}\). The operations 0 and \(n \times m + 1\) are the dummy operations which represent the initial and the last operations, respectively. A dummy operation is used to model the JSSP problem and does not need any processing time. Furthermore, let T and P denote the fixed processing time and the preceding operations.

For an \(n\times m\) JSSP, the problem can be modeled on a set of m machines to process a set of \(n\times m\) operations. An operation can be scheduled for an appointed free machine. A precedence constraint is used to schedule Operation i-th after finishing \(P_{i}\). \(t_{i}\) is the processing time of Operation i on a given machine.

The objective fitness function can be formulated to minimize makespan \(C_{max}\) as follows:

$$\begin{aligned}&Fitness=minimize \,O_{n\times m+1} ( {C_{max}}) \end{aligned}$$
(1)
$$\begin{aligned}&O_q \le O_i -t_i ,\qquad i=0,1,2,\ldots ,n\times m+1;q\in P_i \end{aligned}$$
(2)
$$\begin{aligned}&\sum \limits _{i\in T(t)} \omega _{im} \le 1, \quad m\in M, \quad t\ge 0 \end{aligned}$$
(3)
$$\begin{aligned}&O_i \ge 0,\qquad i=0,1,2,\ldots ,n\times m+1 \end{aligned}$$
(4)

where \(\omega _{im}\) is the weight of setting for Operation i initiating Machine m and it also can be set to the probabilities for diversity-enhanced solutions (Wang et al. 2013). The constraint on precedence relationships is defined by Eq. (2). The constraint on one machine can process at most one operation at a time that is indicated in Eq. (3). The completion time of operations must be positive about the constraint as indicated in Eq. (4).

Parallelized bat algorithm with a communication strategy

In the parallel structure, several groups are created by dividing the population into subpopulations to construct the parallel processing. Each of the subpopulations evolves independently in regular iterations. A good solution based on the best fitness evaluation is selected to continue next periods. After a communication scheme is triggered, bad areas of the solution space are eliminated and exploration of promising regions is carried out. The bat-inspired algorithm should be reviewed briefly as follows the subsection, before analyzing and designing the communication strategy.

Bat-inspired algorithm

Original BA (Yang 2010) simulates parts of the echolocation characteristics of the micro-bat in a simple way. Three major characteristics of the micro-bat are employed to construct the basic structure of BA. The micro-bat, one of species of the bat is a famous example of extensively using the echolocation. Hence, the first characteristic is the echolocation behavior. The second characteristic is the frequency that the micro-bat sends out. The frequency f with a variable wavelength \(\lambda \) and the third characteristic is the loudness that the micro-bat uses to search for prey. The basic concepts of BAs can be described as follows:

  1. 1.

    Bats fly randomly with velocity \(v_{i}\) at position \(x_{i}\). They can adjust the wavelength (or frequency) of their emitted pulses and adjust the rate of pulse emission r \(\in \,[0, 1]\), depending on the proximity of their target.

  2. 2.

    There are many ways to adjust the loudness. For simplicity, the loudness is assumed to be varied from a positive large \(A_{0}\) to a minimum constant value, which is denoted by \(A_{min}\).

The movement of the virtual bat is simulated as follows:

$$\begin{aligned} f_i= & {} f_{min} +\left( {f_{max} -f_{min} } \right) {*}\,\,\beta \end{aligned}$$
(5)
$$\begin{aligned} v_i^t= & {} v_i^{t-1} +\left( {x_i^{t-1} -x_{best} } \right) {*}\,\,f_i \end{aligned}$$
(6)
$$\begin{aligned} x_i^t= & {} x_i^{t-1} +\hbox {v}_{\mathrm{i}}^{\mathrm{t}} \end{aligned}$$
(7)

where, f is the frequency used by the bat seeking for its prey; \(f_{min}\) and \(f_{max}\), represent the minimum and maximum value, respectively. \(x_{i}\) denotes the location of the i-th bat in the solution space; \(v_{i}\) represents the velocity of the bat, t indicates the current iteration, \(\beta \) is a random vector, which is drawn from a uniform distribution, \(\beta \in [0, 1]\); and \(x_{best}\) indicates the global near best solution found so far over the entire population. In addition, the rate of the pulse emission from the bat is considered in the process. The micro-bat emits the echo and adjusts the wavelength depending on the proximity of their target. The pulse emission rate is denoted by the symbol \(r_{i}\), and \(\in \, [0, 1]\), where the suffix i indicates the i-th bat. In every iteration, a random number is generated and compared with \(r_{i}\). If the random number is greater than \(r_{i}\), a local search strategy, namely, random walk is detonated. A new solution for the bat is generated by Eq. (8):

$$\begin{aligned} x_{new} =x_{old} +\varepsilon A^{t} \end{aligned}$$
(8)

where \(\varepsilon \) is a random number and \(\varepsilon \in [-1, 1]\); it represents the average loudness of all bats at the current time step. After updating the positions of the bats, the loudness \(A_{i}\) and the pulse emission rate \(r_{i}\) are updated only when the global near best solution is updated and the randomly generated number is smaller than \(A_{i}\). The updates of \(A_{i}\) and \(r_{i}\) are operated by Eqs. (9) and (10):

$$\begin{aligned} A_i^{t+1}= & {} \alpha A_i^t \end{aligned}$$
(9)
$$\begin{aligned} r_i^{t+1}= & {} r_i^0 \left[ {1-e^{-\gamma t}}\right] \end{aligned}$$
(10)

where, \(\alpha \) and \(\gamma \) are constants.

Communication strategy

In our previous work (Tsai et al. 2014), has proven that the parallel approach to BA is the faster and more accuracy than original one by providing the communication strategies for processing parallel of the swarm of bats in different subgroups. The swarm of bats in BA is divided into G subgroups. Each subgroup evolves from the BA optimization independently, i.e., each subgroup has its own bats and the finest solution. These finest bats among all the bats in a group will be migrated to other groups to replace the poorer bats of that group and update for each group after running every fixed number of iterations. Several partitions could be run in parallel and then merged. The child processes are halted and their results are compared. After communicating, bad areas of the solution space are eliminated and the promising regions are explored. Let \(G_{j}\) be the number of agents of the subgroup, where j is the index of the subgroup. While \(t \cap R \ne \phi \), where t is current iteration, and R is the fixed iterations, k agents (where the top k fitness in \(G_{j}\)) will be copied to \(G(j+1)\) to replace the same number of agents with the worst fitness, where \(j = 0, 1,2,\ldots , G.\) The diagram of the parallelized BA with a communication strategy is shown in Fig. 1.

Fig. 1
figure 1

The diagram of PBA with a communication strategy

Full size image

The steps can be described as follows:

  1. 1.

    Initialization: Generate bat population and divide it into G subgroups. Each subgroup is initialized by BA independently. Assign \(R\hbox {-}th\) number of iterations for executing \(X_{ij}^T\) solutions for \(N_{j}\) bats in the j-th group, \(i= 0, 1,{\ldots }, N_{j-1};\, j = 0, 1,{\ldots }, G-1\), where G is the number of groups, Nj is the \(j\hbox {-}th\) subpopulation size and t is the current iteration and set to 1.

  2. 2.

    Evaluation: Evaluate the value of \(f (X_{ij}^t )\) for bats in j-th group.

  3. 3.

    Update: Update the velocity and bat positions using Eqs. (5), (6) and (7).

  4. 4.

    Communication strategy: Migrate k best bats among \(G^{t}_{j}\) to the \((j+1)\hbox {-}th\) group \(G^{t}_{j+1}\), mutate \(G^{t}_{j+1}\) by replacing k poorer bats in that group and update all of the group in each R iterations.

  5. 5.

    Termination: Repeat Step 2 to Step 5 until the predefined value of the function is achieved or the maximum number of iterations has been reached. Record the best value of the function \(f(X_{ij}^t )\) and the best bat position among all the bats \(X_{ij}^t \).

Parallel bat algorithm for JSSP

JSSP is a combinatorial problem, and its solution space is discrete. However, the encoding scheme for PBA is continuous, so it cannot be applied to solve JSSP directly. In order to apply PBA to JSSP, a direct mapping relationship between the job sequence and the vector of individuals in PBA must be constructed as a discrete one. To do so, a random-key encoding scheme (RES; Bean 1994) is used to combine with PBA to solve this issue. The parallel processing with communication strategy and the embedding of the random walk of a local search strategy in proposed algorithm PBA is an effective way to obtain a more effective solution. The following example illustrates the JSSP problem with three jobs \((n=3)\) and three machines \((m=3)\). The operations must be processed for jobs in Table 1. The initiated machine order for each operation and the processing times are provided in Tables 2 and 3.

Table 1 Jobs and operation index in a \(3\times 3\) JSSP
Full size table

The satisfied operation ordering with the stated constraint Eqs. (1–4) is a feasible schedule. The feasible result from this JSSP is 1,4,7,5,2,8,3,6,9 with the obtained makespan of 17. Figure 2 shows the Gantt chart of the schedule of this \(3\times \hbox {3JSSP}\).

Table 2 Machine allocation in a \(3\times 3\) JSSP
Full size table
Table 3 Operation times in \(3\times 3\) JSSP
Full size table
Fig. 2
figure 2

A sample Gantt chart for feasible schedule for example of a \(3\times 3\) JSSP

Full size image

Representation of individuals in PBA for JSSP

Random key encoding scheme can be used to transform a position in a continuous space to a discrete space. The searching space is created in an \(n\times m\) dimensions space for n jobs on m machines JSSP. The location of a bat consists of \(n \times m\) dimensions and is represented with \(n\times m\) real numbers. In order to simulate an operation permutation sequence of JSSP, the \(n\times m\) real numbers are transformed into an integer series from 1 to \(n\times m\) by the RES. Each integer number represents an operation index according to its ordering in all \(n \times m\) real numbers. A real vector in the RES is sorted through an ascending order for an integer series \((\tau _1 , \tau _2 ,\ldots , \tau _k )\) in which each integer \(\tau _k\) indirectly represents an operation order of a job, where \(1 \le k\le n\times m\). Because each job must go through m machines to complete its work, a job must have m operations that are scheduled for a preceding constraint. For this constraint, the job index can be calculated by \((1+\tau _k \,mod \,n)\), where n is the number of jobs. An operation sequence is figured out by the integer series transformation. Scanning from the left to the right, each job index has m occurrences, which correspond to the number of operations for a job. The operation order can be satisfied with the preceding constraint because the operation permutation is feasible.

Fig. 3
figure 3

The RES processing for an individual representation in a \(3\times 3\) JSSP

Full size image

Figure 3 illustrates an example of processing from an RES virtual space to a feasible operation permutation in the \(3\times 3\) JSSP solution space. It is supposed that the location of a bat in an RES virtual space is (10.2, 2.5, 7.5, 6.7, 1.3, 5.3, 4.2, 8.1, 9.5). It can be encoded to an integer series (9, 2, 6, 5, 1, 4, 3, 7, 8) by sorting the \(3\times 3\) real numbers in an ascending order, i.e., 1.3 is the smallest number, it is then ranked to 1 and so on. In this integer series, the integers 9, 6 and 3 indicate that the operations belong to Job 1 because \(\hbox {(9 mod 3)} + 1 = 1, \hbox {(6 mod 3)} + 1 = 1 \hbox { and}\, \hbox {(3 mod 3)} + 1 = 1\). The integers 1, 4 and 7 indicate that the operations belong to Job 2, because \(\hbox {(1 mod 3)} + 1 = 2, \hbox {(4 mod 3)} + 1 = 2 \hbox { and (7 mod 3)} + 1 = 2\). The integers 2, 5 and 8 indicate that the operations belong to Job 3, because \(\hbox {(2 mod 3)} + 1 = 3, \hbox {(5 mod 3)} + 1 = 3 \hbox { and (8 mod 3)} + 1 = 3\), respectively. An operation permutation (1, 3, 1, 3, 2, 2, 1, 2, 3) corresponding to job indexes is obtained. Scanning from the left to the right for these operations, the first 1 means the first operation of job 1, corresponding to \(o_{11}\), the second 1 means the second operation of job 1, corresponding to \(o_{12}\) and the third 1 means the third operation of job 1, corresponding to \(o_{13}\). According to this scanning process, the partial series (2, 2, 2) corresponds to \((o_{21}, o_{22}, o_{23})\) and (3, 3, 3) corresponds to \((o_{31}, o_{32,} o_{33})\). After scanning the job index series from the left to the right, the permutation (1, 3, 1, 3, 2, 2, 1, 2, 3) corresponds to an operation sequence \((o_{11}, o_{31}, o_{12}, o_{32}, o_{21}, o_{22}, o_{31}, o_{23}, o_{33})\) as shown in Fig. 3. The operation sequence represented by this encoding scheme is always a feasible solution of JSSP.

Neighborhood operators

Because the solutions space of sequential operations in JSSP are discrete, PBA must be constructed in the discrete solutions based on the mapping relationship between the job sequence and the vector of individuals. For improving the diversity of population, enhance the quality of the solution and process parallel strategies, several operations have to be used the application methods of the diversity-enhanced solutions (Wang et al. 2013) and a wrapper feature selection (Rodrigues et al. 2014). These operations include swapping, insertion, inversion and long distance communication schemes based on Hamming distance methods. They could be defined as follows.

Swap is to choose two different positions of an operation permutation sequence randomly and swap them.

Insert is to choose two different positions of an operation permutation sequence randomly and insert the back one before the front.

Inverse is to inverse the subsequences between two different random positions of an operation permutation sequence.

Long distance communicate is to choose a subsequence in a random interval of another random the operation permutation sequence and replace the corresponding part of the subsequence.

For example, when two positions of an operation sequence in an individual need to exchange the order, the “swap” operator has to be used. Compare the makespan before being exchanged and after being exchanged, if the makespan after being exchanged is better, then the new permutation operation of this individual of the current solution will be updated.

Communication strategies

As mentioned above, the parallelization of algorithms is based on dividing (partitioning) the problem so that several partitions could be run in parallel and then merged. This idea is to run several processes for the entire problem in parallel and periodically compare the results. The search is then continued by all the processes from a common good solution. A main process reads the problem definition. A set of child processes on separate processors is then created for running an operation sequence of each machine by the communication schemes. After running specified time interval, the child processes are halted and the main process compares their results. A good solution for the child process is selected to continue next specified time interval. The promising area of the solution space will be explored. To be satisfied the constraint in Eq. (3), a machine can process only one operation at a time, total of the distributed weights for the operation diversity of individual is equal to or less than one. To do so, a solution enhancement algorithm based on the neighborhood operations, (named as COM) is employed as shown in Fig. 4. \(w_s , w_{i } , w_{inv}\) and \(w_{long}\) means the probability of executing the swapping scheme, the insertion scheme, the inversion scheme and the long distance movement scheme, respectively.

Table 4 Computational result comparison of PBA, PSO and BA methods for instances FT and LA of the test benchmark
Full size table
Fig. 4
figure 4

The pseudo-code of communication strategy (COM scheme)

Full size image

Objective function

The objective function is to minimize makespan with satisfied constrains in Eqs. (1–4). Evaluation for this objective function is employed in the transformed solution space of JSSP by applying the SA algorithm (Kirkpatrick 1983). The SA algorithm has been successfully applied to many combinatorial optimization problems (Koulamas et al. 1994). The key function of SA is to allow occasional alternations to accept worsened solutions in order to increase the probability of jumping away from a local optimum and obtaining a better solution. In an SA algorithm, a new state \(s'\) is accepted with a given probability min \(\{1, exp^{\Delta /T}\}\) if \(\Delta \) is greater than or equal to zero, where T is a control parameter referred as temperature, \(\Delta = f(s')-f(s)\), and f() is objective function. The temperature T is defined by the user, and T is decreased iteration by iteration according to a referred cooling schedule from high to low. The SA algorithm is executed from high temperature until T is lower than a user-defined final temperature \(T_f \) which is a value near to zero. The individual’s position can be accepted as a new position of the individual if one random probability is greater than min \(\{1, exp^{\Delta /T}\}\). It means the makespan can be made improvement; otherwise, the previous position for the individual could be kept. Figure 5 shows the pseudo code for evaluating the object function namely the CMX method.

Fig. 5
figure 5

The pseudo-code of the objective function (CMX method)

Full size image

Discrete PBA for JSSP

Discrete PBA for JSSP is based on the integration of the RES, communication strategy scheme (COM) and makespan (CMX) into the BA. In this method, an artificial bat is represented by a real vector as shown in row 1 of Fig. 3. Every bat flies its location in the RES space by Eqs. (6) and (7), and the objective function of one bat corresponding to the solution space of JSSP can be evaluated by the transformation from RES space to a solution space of JSSP by Eqs. (1–4). For the communication strategy of parallel processing, bad areas of the solution space are eliminated and exploration of promising regions is carried out. The RES encoding scheme provides a search space for the continuous PBA and an easy way to encode the representation of artificial bat in PBA. The weight distribution in COM communication strategy scheme provides a selected bat, which can be in a better location than the previous one. Then, each bat can fly to a new location according to Eqs. (6), (7) and (8). The process of objective function CMX scheme and PBA are executed until it obtains the optimal solution or the maximum iteration number is reached (Fig. 6).

Fig. 6
figure 6

The pseudo-code of PBA for JSSP

Full size image

Experimental results

The performance of the proposed method of the PBA for the JSSP is examined by using some test problems taken from the OR- Library (Beasley 1990) as the test benchmarks. Four three instances from two classes of standard JSSP test problems included Fisher and Thompson (Fisher and Thompson 1963) with instances FT06, FT10, and FT20, and Lawerence (Lawler et al. 1993) with instances LA01–LA40.

The parameters setting for both PBA and BA as referring to (Tsai et al. 2014); the maximum of location is limited to \(n\times m\) and the population size of the swarm is set to 30. The initial weight for COM scheme for the entire procedure of the PBA for the JSSP algorithm is set to be 0.01. The initial temperature T is set to be the difference between the makespan of the selected bat and the best known solution, \(T_{f}\) is set to be 0.1 and \(\beta \) is set to be 0.97. Each instance contains the full 200 iterations. The evaluated experimental results compared with the obtained using the BA and PSO (Ge et al. 2008) methods are listed in Table 4. The Gantts chart and convergences curves of the first two instances are illustrated in Figs. 7, 8, 9, 10 and 11.

Fig. 7
figure 7

Convergence comparison of BA, PSO and PBA methods for a \(6\times 6\) JSSP and their Gantt

Full size image
Fig. 8
figure 8

Convergence comparison of BA, PSO and PBA methods for a \(10\times 10\) JSSP

Full size image
Fig. 9
figure 9

The Gantt of PBA method for a \(10\times 10\) JSSP

Full size image
Fig. 10
figure 10

The Gantt of PSO method for a \(10\times 10\) JSSP

Full size image
Fig. 11
figure 11

The Gantt of BA method for a \(10\times 10\) JSSP

Full size image

Figure 7 shows the convergence rate of the first instances FT06 with size \(6\times 6\) and their plot Gantts of the three methods, namely PBA, PSO and BA for JSSP. Figures 8, 9, 10 and 11 show the convergence rate of the second instances FT10 with size \(10\times 10\) JSSP and their plot Gantts of the PBA, PSO and BA methods. It is clear that the proposed PBA method converges faster than the of BA and PSO methods.

In Table 4, instance means the problem name, size means the problem size n jobs on m machines, BKS means the best known solution for the instance (Muth and Thompson 1963), Best means the best solution found by each algorithm, and RD means the percentage of the deviation with respect to the best known solution for the proposed method and PSO method, namely HIA (Ge et al. 2008). The boldface in Table 4 represents the better solution for one instance between PBA and PSO methods. According to the best known solutions presented in Table 4, the PBA method outperforms the BA method in 36 instances and outperforms PSO method in 10 instances. However, the PBA method performs slightly an inferior the PSO method in three other instances. In general, the PBA method can obtain the optimal area in the search space with diversity, and can get better solution than the PSO and BA methods for the JSSP scheduling problems.

The comparisons of the PBA, PSO and BA methods for testing the stable and diversity by averaging experimental results of five runs was shown in Table 5. Each run is executed 200 iterations. Instances FT06, FT10, FT20 and the first instance of other type instance set are selected as test benchmark. BKS and Best are the same meaning as those in Table 4. ARD means the relative deviation of the average solution and Avg the average of results for 5 runs, respectively. The boldface in Table 5 represents the obtained solutions for instances of the used methods PBA, PSO and BA could have been reached the BKS. Observing Table 5, the difference between the Best and the BKS, and the difference between the Avg and the BKS are within 1% and 2% for PBA and PSO methods respectively. However, this figure is higher than 2% for BA method. Because of the BA method is easy to be trapped in a local optimal and cannot find a better solution. Above experimental results show that the proposed method can obtain the better solutions than those obtained of the PSO and BA methods by providing the diversity-enhanced bats to speed up solutions.

Table 5 Average experimental result comparison of PBA, PSO and BA methods
Full size table

Conclusion

In this paper, a solution to the NP-hard job shop scheduling problems (JSSP) based on parallel versions of bat algorithm (PBA), RES, communicating strategy schemes (COM) and makespan scheme (CMX) was presented. The aim at the parallel BA with communication strategies is to correlate individuals in swarms and to share the computation load among numerous processors. In this situation, the entire problem has several partitions that could be run in parallel and then merged. After running specified time intervals, the child processes are halted and their results compared in the main process. A good solution for the child process is selected to continue with. A good solution might be the one with the best fitness. After triggering communication schemes, bad areas within the solution space are eliminated and the exploration of promising region is carried out. In the proposed method, a location of a bat composed of \(n\times m\) real numbers can be represented in the discrete solution space of JSSP by the encoding RES scheme. A speed up of selection solutions under the constraint is figured out by the COM schemes. The objective function of the bat corresponding to the solution space of JSSP could be evaluated by the application the SA algorithm to minimize the makespan. In the experiments, variety of sizes in instances of job shop scheduling benchmarks in the literature were used to test the behavior of convergence, the accuracy, and the speed of the proposed method. The results were compared with those obtained using the BA and PSO methods. The comparison indicates that the proposed method provides competitive results.