Keywords

1 Introduction

In many manufacturing environments, the job often refers to a set of tasks to be carried out by machines over semi-finished goods or raw materials in order to obtain a final product. Lot-steaming is a production layout in which every job can be split into a number of smaller sub-lots. When a sub-lot is completed, it can be immediately transferred to the downstream machine. By this splitting technique, the idle time on successive machines can be reduced, and thereby reducing productive cycle, accelerating the manufacturing process and enhancing the production efficiency. The goal for this problem is to find a solution (or a sequence) that optimizes a given objective function, i.e., maximum completion time minimization or makespan, the total flow time, the tardiness time and the earliness time.

For the lot-streaming problem in flow shop environment, Sarin et al. [1] presented a polynomial-time procedure to determine the number of sub-lots of a single-lot, multiple-machines flow shop lot-streaming problem. In this work, the authors minimized the unified cost-based objective function that comprised criteria pertaining to makespan, mean flow time, work-in-process, sublot-attached setup and transfer times. Pan et al. [2] presented a novel estimation of distribution algorithm (EDA) to minimize the maximum completion time, in which an estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. Defersha and Chen [3] first proposed a mathematical model for the lot-streaming problem in multi-stage flow shops where at each stage there are unrelated parallel machines, and then proposed genetic algorithm based on parallel computing platforms to solve the above problem. Numerical examples showed that the parallel implementation greatly improved the computational performance of the developed heuristic. To minimize the mean weighted absolute deviation from due dates of the lot-streaming flow shop scheduling, Yoo and Ventura developed a heuristic based on pairwise interchange strategy [4]. Chakaravarthy et al. [5] proposed a differential evolution algorithm (DE) and particle swarm optimization (PSO) to evolve the best sequence for makespan/total flow time criterion of the m-machine flow shop involved with lot-streaming and set up time. Following that Chakaravarthy et al. [6] adopted an improve sheep flock heredity algorithm and artificial bee colony algorithm, respectively, to solve lot-streaming flow shop with equal size sub-lot problems. For the same problems, Sang et al. [7] designed an effective iterated local search algorithm, in which an insertion neighborhood and a simulated annealing-typed acceptance criterion are utilized to generate good solutions.

In most practical manufacturing enterprises, there is no intermediate buffer between machines to store completed jobs. Therefore, these completed jobs have to remain in the current machine, until its following one is available for processing, which increases waiting time and the production period. Previous research has already been done to tackle a blocking flow shop (BFS) scheduling problem [8], so as to improve the production efficiency. Similarly, in a lot-streaming flow shop (LSFS) scheduling problem, each sublot will also be blocked when there is no intermediate buffer to store completed sublots. These practical scenarios encourage us to apply the blocking constraint to a LSFS scheduling problem, and form a blocking LSFS (BLSFS) scheduling problem [9].

Very recently, a new metaheuristic intelligence approach named the Migrating Birds Optimization (MBO) algorithm, which simulates the V flight formation of migrating birds, as the name implies, was presented by Duman [10]. For the scheduling problems, Tongur and Ülker [11] first applied the basic MBO algorithm to optimize the discrete flow shop sequencing problem. Following that Pan and Dong designed an improved MBO (IMBO) algorithm to minimize the total flowtime of the hybrid flow shop scheduling [12]. In this work, the authors presented a diversified method to initialize population with high quality, and constructed a mixed neighbourhood based on insertion and pairwise exchange operators to generate promising neighbouring solutions for the leader and the following birds. Similarly, Niroomand et al. [13] also proposed modified MBO (MMBO) algorithm to optimize closed loop layout with exact distances in flexible manufacturing systems, which are different from IMBO considered by Pan and Dong. In MMBO, the authors employed crossover and mutation operators to yield the neighbor regeneration.

For the above literature, the simulation experimental results have verified that the MBO algorithm is appropriate and competitive for solving continuous and discrete optimization problems. To the best of our knowledge, the MBO algorithm has not been applied to the LSFS scheduling problem with blocking. With the above motivations, we proposed an improved MBO (iMBO) algorithm to solve the BLSFS scheduling problem.

The rest of this paper is organized as follows. After this brief introduction, in Sect. 2, the description of BLSFS scheduling problem is stated. Next, Sect. 3 presents the proposed algorithm. Section 4 provides the experimental results. Finally, the paper ends with some conclusions in Sect. 5.

2 BLSFS Scheduling Problem

For each job, it can be processed at the ith machine after its front job completed at the ith machine, in which all the sub-lots of the same job should be processed continuously. At any time, for each machine, it can process at most a sub-lot, and a sub-lot can be processed on at most one machine at a time.

In the sequel, we assume that there are n jobs and m machines; denote the job sequence (solution) as π = (1, 2, …, n); and let lj be the number of sublots in job j. All sublots of the same job have to be processed on each of m machines in the same series. The processing time of each sublot of a job j on machine t is pj, t. We use Sj, t, e and Cj, t, e to represent the start and the completion time of the e-th sublot in job j on machine t, respectively, where e = 1, 2, …, lj; dj refers to the due date of job j.

The completion time of each job on each machine can be calculated using the following equations.

$$ \left\{ {\begin{array}{*{20}l} {S_{1,1,1} = 0} \hfill \\ {C_{1,1,1} = S_{1,1,1} + p_{1,1} } \hfill \\ \end{array} } \right. $$
(1)
$$ \left\{ {\begin{array}{*{20}l} {S_{1,t,1} = C_{1,t - 1,1} } \hfill \\ {C_{1,t,1} = S_{1,t,1} + p_{1,t} } \hfill \\ \end{array} } \right.\quad t = 2,3, \ldots ,m $$
(2)
$$ \left\{ {\begin{array}{*{20}l} {S_{j, 1, 1} = { \hbox{max} }\{ C_{{j - 1, 1,l_{j - 1} }} ,S_{{j - 1, 2,l_{j - 1} }} \} } \hfill \\ {C_{j, 1, 1} = {\text{S}}_{j, 1, 1} + {\text{p}}_{j, 1} } \hfill \\ \end{array} } \right.\quad j = 2,3, \ldots ,n $$
(3)
$$ \left\{ {\begin{array}{*{20}l} {S_{j,t,1} = \hbox{max} \{ C_{j,t - 1,1} ,S_{{j - 1,t + 1,l_{j - 1} }} \} } \hfill \\ {C_{j,t,1} = S_{j,t,1} + p_{j,t} } \hfill \\ \end{array} } \right.\quad \begin{array}{*{20}l} {t = 2,3, \ldots ,m - 1} \hfill \\ {j = 2,3, \ldots ,n} \hfill \\ \end{array} $$
(4)
$$ \left\{ {\begin{array}{*{20}l} {S_{j,m,1} = \hbox{max} \{ C_{j,m - 1,1} ,C_{{j - 1,m,l_{j - 1} }} \} } \hfill \\ {C_{j,m,1} = S_{j,m,1} + p_{j,m} } \hfill \\ \end{array} } \right.\quad j = 2,3, \ldots ,n $$
(5)
$$ \left\{ {\begin{array}{*{20}l} {S_{j,1,e} = \hbox{max} \{ C_{j,1,e - 1} ,S_{j,2,e - 1} \} } \hfill \\ {C_{j,1,e} = S_{j,1,e} + p_{j,1} } \hfill \\ \end{array} \quad \begin{array}{*{20}l} {e = 2,3, \ldots ,l_{j} } \hfill \\ {j = 1,2,3, \ldots ,n} \hfill \\ \end{array} } \right. $$
(6)
$$ \left\{ {\begin{array}{*{20}l} {S_{j,t,e} = \hbox{max} \{ C_{j,t - 1,e} ,S_{j,t + 1,e - 1} \} } \hfill \\ {C_{j,t,e} = S_{j,t,e} + p_{j,t} } \hfill \\ \end{array} } \right.\quad \begin{array}{*{20}l} {e = 2,3, \ldots ,l_{j} } \hfill \\ {t = 2,3, \ldots ,m - 1} \hfill \\ {j = 1,2,3, \ldots ,n} \hfill \\ \end{array} $$
(7)
$$ \left\{ {\begin{array}{*{20}l} {S_{j,m,e} = \hbox{max} \{ C_{j,m - 1,e} ,C_{j,m,e - 1} \} } \hfill \\ {C_{j,m,e} = S_{j,m,e} + p_{j,m} } \hfill \\ \end{array} } \right.\quad \begin{array}{*{20}l} {e = 2,3, \ldots ,l_{j} } \hfill \\ {j = 1,2,3, \ldots ,n} \hfill \\ \end{array} $$
(8)

Equations (1) and (2) give the completion time of the first sublot of the first job at m machines. Equations (3–5) computes the completion time of the first sublot of job j (j = 2, 3, …, n) at machine t (t = 1, 2, …, m), in which the values of S(j-1),2,l (j-1) and S(j-1),t+1,l (j-1) are obtained by Eqs. (5 and 6), respectively. Equations (6–8) calculates the completion time of the e-th (e = 2, 3, …, lj) sublot of job j (j = 1, 2, …, n) at machine t (t = 1, 2,…, m).

The start time of the first sub-lot of the first job on the first machine is equal to zero, that is, \( S_{1,1,1} = 0 \). The makespan of the job permutation, \( \pi \), is equal to the time when the last job in the processing sequence is finished at machine m. Its value can be represented according to Eq. (9).

$$ C_{\hbox{max} } (\pi ) = C_{{n,m,l_{n} }} $$
(9)

3 The Proposed iMBO for the BLSFS Scheduling Problem

3.1 Initialization Population

To generate an initial population with a certain level of quality and diversity, many heuristics, i.e., NEH, MME and PFE, have been successfully adapted to initialize the seeds of the population [8]. But, they can only generate a single solution. If some good seeds in the initial population can be generated, the efficiency convergence of the whole algorithm will be enhanced. Therefore, the above idea is employed in this study. That is, a multiple-based MME initial strategy is proposed to yield \( \beta \) solutions with high quality, and a random method is adopted to generate the rest solutions so as to maintain the diversity of the population. The detailed process of generating \( \beta \) solutions is shown in Algorithm 1.

figure a

3.2 Improving the Leading Solution

Insertion, swap and inverse operators are commonly used to produce a promising neighboring solution, which can enhance the solution’s exploitation ability by slightly disturbing the neighboring solution. For more details about the above operators, please refer to [8].

In this section, three strategies based on insert, swap, and inverse operators are proposed: (1) perform insert once; (2) apply swap one time; (3) conduct inverse once. Generally speaking, more strategies generate different solutions with a larger probability than a single strategy, and avoid the population trapping in local optima.

We randomly chose one of the above four strategies to generate solutions, in which the best neighbor solution is selected to update the leading solution, and the remaining solutions are put into two shared neighbor sets, respectively.

3.3 Improving the Other Solutions in the Population

The process of improving the other solutions in the population plays an important role, whose contribution is that it can lead the offspring to the global good solution, and improve the convergence of the algorithm. The estimation of distribution algorithm (EDA) can utilize the valued information of solutions in the population to construct a probabilistic model, and then estimate the probability distributions of good solution to build new ones. In this paper, the sequence-based discrete EDA is given to generate a number of sequences so as to improve solutions in the population.

The basic EDA mainly includes four steps [14]: First, select PS promising solutions from the original population by computing fitness value of each individual, and then put them into a candidate population \( [\eta_{i,j} ]_{PS \times n} \); Second, build a probability distribution model \( [\xi_{i,j} ]_{n \times n} \) based on the candidate population; Third, generate a new solution through learning and sampling from according to the constructed probabilistic model \( [\xi_{i,j} ]_{n \times n} \). Repeat the above third step for generating some new solutions. Last, update the population by evaluating the objective value of each solution in the population, and delete some bad solutions.

The detailed description of the proposed EDA is given as follows:

figure b

3.4 Improving the Other Solutions in the Population

In this work, the purpose of the local search is to generate a better solution from the neighborhood of a given solution. We adopt an insert-neighborhood-based local search, which has been regarded as superior to the swap or exchange neighborhood. Furthermore, we try to present a simple algorithm with few parameters, so some relative algorithms such as taboo search and simulated annealing algorithm are not applied. In this paper, we apply the local search to the solutions generated in Subsect. 3.2 with a small probability of pls. That is, a uniform random number r is generated from 0 and 1, if r < pls, the solution will employ several insertion operators. Otherwise, the solution does not perform the local search.

4 Experiments

In this section, the proposed iMBO is compared with EDA [2], DIWO [7], and MMBO [12] algorithms to evaluate the performance of the proposed algorithm. The test instance set is composed of 150 different instances, which are divided into 15 subsets and each subset consists of 10 instances with the same size. These subsets range from 10 jobs and 5 machines to 500 jobs and 20 machines [15]. Each instance is independently executed five replications. For each instance, we independentlly run each method 5 times, record the minimal makespan, and obtain the average relative percentage difference of 5 times. For all instances in a group, we obtain the above average relative percentage differences, and denote their average as ARPD. Denote the makespan of the jth instance provided by the ith algorithm in the tth run as \( C_{j,t}^{i} \), \( C_{j}^{R} \) is the best known solution provided so far by existing algorithms for the specified problem or by our proposed algorithms. From the following Eq. (12), we can see that the smaller the average relative percentage difference APRD is, the better result the algorithm produces. Denote APRD obtained by the ith algorithm as \( ARPD_{i} \), then \( ARPD_{i} \) can be stated as follows.

$$ APRD_{i} = \frac{1}{50}\sum\limits_{j = 1}^{10} {\sum\limits_{t = 1}^{5} {\frac{{C_{j,t}^{i} - C_{j}^{R} }}{{C_{j}^{R} }}} \times 100} $$
(12)

All these algorithms were implemented with C++ in a PC environment with Pentium(R) Dual 2.8 GHZ and 2 GB memory. Following Yoon, Ventura, and Tseng and Liao [13], the related data for each LSFS scheduling problem are given according to the discrete uniform distributions as below. The number of solutions generated by strategies 1 and 2 are both 6, respectively, in the initialization of the population. The values of the rest parameters are set in Table 1.

Table 1. Parameter setting
Full size table

Tables 2 and 3 report APRD over each subset for computation time T = 5, 15, respectively.

Table 2. Performance comparison of EDA, DIWO, MMBO and NMBO algorithms (T = 5)
Full size table
Table 3. Performance comparison of EDA, DIWO, MMBO and NMBO algorithms (T = 10)
Full size table

It can be seen from Table 2 that the overall mean APRD value yielded by the iMBO algorithm is equal to 0.48, which is much smaller than 0.72,0.67,0.61 generated by the EDA, DIWO and MMBO algorithm. As the problem size increases, the superiority of the iMBO algorithm over EDA, DIWO and MMBO algorithms increases. On the other side, The results reported in Table 3 further justifies the superiority of the iMBO algorithm over the EDA, DIWO and MMBO algorithms for computation time T = 10. Thus, we can conclude that the presented NMBO algorithm outperforms the EDA, DIWO and MMBO algorithms for lot-streaming flowshop problems with makespan criterion.

Table 4 reports the two-side Wilcoxon rank sum tests of iMBO, EDA, DIWO and MMBO algorithms with significant level equal to 5%. In the Table 4, there are two values, i.e., p value and h value. P is the probability of observing the given result by chance if the null hypothesis is true. When h equals 1, it indicates that the results obtained by the two compared algorithms are obviously different. When h equals 0, it denotes that the difference between the two algorithms is not significant at 5% significant level. From the Table 4, the h values of the compared algorithms are equal to 1, and the p values are close to 0. Thus, it can be demonstrated that iMOB proposed in this paper is significantly different from the other compared algorithms.

Table 4. Wilcoxon two-sided rank sum test of the iMBO, EDA, DIWO and MMBO algorithms
Full size table

5 Conclusions

In this paper, iMBO is proposed to minimize makespan for the BLSFS scheduling problem. In order to perform exploration for promising solutions within the entire solution space, iMBO with an effective population initialization approach is developed. A simple but effective local search algorithm was employed. To further enhance the proposed algorithm, we adopt EDA to obtain solutions for the rest migrating birds. Computational experiments are given and compared with the results yielded by the existing EDA, DIWO, and MMBO algorithms. The future work is to apply iMBO to other optimization problems and encourage us to extend the ideas proposed to the different objective functions or multi-objective in scheduling problems.