1 Introduction

In recent years, smart manufacturing has been experiencing an explosive growth and has now become one of the dominant factors for enterprises to compete in the fiercer global competition (Yang et al. 2018). The production of many products, e.g., mobile phones, aircraft, and automobiles, needs to be first processed by several semi-product manufacturers, and then it is completed by assembly manufacturers, as is shown in Fig. 1. It is of great significance to make smart decisions for semi-product manufacturers and assembly manufacturers in the manufacturing system to reduce production duration and increase profit. To cope with global competition, some researchers have investigated optimization problems in assembly lines (Framinan et al. 2019), where they have proposed various solution methods and have summarized development trends of assembly production scheduling. In addition, Renna and Perrone (2015) investigated manufacturing systems with multiple manufacturers and stated that coordinating manufacturing is very important in today’s world. Jia and Mason (2009) considered the problem of scheduling orders in a multi-machine manufacturing system. Most previous research has focused on general processing without considering practical specific production features. However, there are a number of practical issues in a real manufacturer system, such as serial-batching production, the learning effect, and the deteriorating effect, which make it more difficult for decision-makers in the manufacturing system to produce efficient schedules. Thus, in this paper, we address an integrated manufacturing optimization problem which covers various practical issues.

Fig. 1
figure 1

The integrated scheduling problem in complex product manufacturing

Full size image

Classical scheduling problems assume that the processing times of jobs are constant values. However, the actual processing time of a job may increase or decrease with changing machine efficiency and human proficiency. These phenomena are called the deteriorating effect and the learning effect (Wang 2007). Gawiejnowicz (2008) systematically summarized various types of deterioration effects, and he also analyzed how these effects affect the optimal scheduling scheme in general scheduling problems. Azzouz et al. (2018) presented a concise overview of learning effects, provided a classification scheme for the different scheduling problems under learning effects, and discussed the relationship between some well-known leaning models. To solve real-life production scheduling problems, many other researchers have also taken the deteriorating effect and the learning effect into consideration. Wang and Cheng (2007) studied a single-machine scheduling problem and constructed time- and position-based job-processing time functions. Considering that there should be an upper limit to proficiency, Wang et al. (2017) investigated a single-machine scheduling problem with a truncated job-dependent learning effect. Yin et al. (2017) considered deteriorating jobs in a parallel machine scheduling problem with potential machine disruptions. Fu et al. (2018) studied scheduling problems with deteriorating and learning effects in an industry 4.0-based manufacturing system.

In a batching scheduling problem, jobs are grouped into batches and processed on the batching machine. This type of production mode can improve the efficiency of the machine, while a setup operation is required before the processing of each batch to ensure the security and quality of the production. Batching scheduling problems commonly exist in semi-product manufacturing (Yin et al. 2016; Ahmadizar and Farhadi 2015) and have drawn much attention in recent years. Mor and Mosheiov (2011) investigated a two-agent single-machine scheduling problem in the context of batch processing. For a batching scheduling problem with transportation, Yin et al. (2013) developed an efficient dynamic programming algorithm under an assumption on the relationships between the cost parameters. Differently, Yin et al. (2015) considered a single-machine batching scheduling problem with rejection costs and developed algorithms with significant improvements. Then, to solve the problem in more complex manufacturing systems, Yin et al. (2018) studied integrated production, inventory, and batch delivery scheduling problems with due date assignments and two competing agents, based on which effective heuristics were proposed. Kress et al. (2018) focused on the total setup cost minimization problem and proposed an approximately optimal algorithm to solve it in polynomial time. Alam and Raza (2018) investigated a batching scheduling problem in a parallel and distributed environment. Shahvari and Logendran (2018) solved a hybrid flow shop batching scheduling problem via two-stage-based hybrid algorithms.

In the assembly scheduling literature, some papers have analyzed makespan minimization problems within a certain factory, typically where the component production and assembly can be finished in a single production flow line (Liao et al. 2015). In these settings, the operator only needs to consider the optimal schedule of the product components on a single machine, and the assembly starts whenever a set of parts is finished. However, in a global manufacturing system, the product components are manufactured by several enterprises located in different places. After being processed by the semi-product manufacturer, the product components are delivered and assembled into the final product by an assembly manufacturer. Roh et al. (2014) investigated the response supply chain in global complexity and stated that improving production capability is a key to the success of firms in the global supply chain. Tao et al. (2017) analyzed the evolution of such a manufacturing system in the environment of information technology.

There is limited existing literature on integrated scheduling models considering the production, assembly, serial-batching processing, the deteriorating effect, and the learning effect simultaneously. Our previous research papers involved such issues as the batching and deteriorating effects, and we focused on the single-stage scheduling problems with multiple machines or a single machine. The comparison of this with existing publications is presented in Table 1. In Pei et al. (2017), we studied the batching scheduling problem with the deteriorating effect as well as the learning effect and proposed several effective heuristics, but the assembly process was not considered. Hence, those proposed methods cannot solve the problem in this work. Lu et al. (2018) investigateda coordinating production and maintenance scheduling problem under the deteriorating effect. The assembly process and the leaning effect are ignored in that model. This paper contributes by considering various significant issues in an integrated scheduling problem and proposes several useful structural properties, based on which effective heuristics and a metaheuristic are developed to make decisions for different participants in the manufacturing system. To the best of our knowledge, the proposed scheduling problem in this paper has not been studied in any existing literature. However, the problem exists in real-life manufacturing and solving the problem is significant for the realization of smart manufacturing, which is the motivation of this paper.

Table 1 Comparisons of previous related literature and the current study
Full size table

The main contributions of this work are stated as follows.

  1. 1.

    We formulated an integrated scheduling model which covers production and assembly. In addition, the features of serial-batching processing, the deteriorating effect, and the learning effect are taken into consideration in our model.

  2. 2.

    For the serial-batching scheduling problem in the production stage, several structural properties are proposed, based on which an optimal algorithm is developed.

  3. 3.

    For the assembly scheduling problem, we give some useful lemmas and design a heuristic which can improve the solution quality.

  4. 4.

    Since the integrated problem is proved to be NP-hard, we develop a LIMA-VNS (less is more approach–variable neighborhood search) to solve the problem. The performance of the LIMA-VNS is validated via computational experiments.

The remainder of this paper is organized as follows: Sect. 2 gives the formulation of the considered integrated scheduling problem. In Sects. 3 and 4, we discuss the subproblems of the integrated model and develop heuristics to solve them, respectively. In Sect. 5, we design a metaheuristic to solve the integrated scheduling problem. Sect. 6 presents the results of computational experiments and analyzes the performance of the involved metaheuristics. Finally, Sect. 7 concludes and gives some future research directions.

2 Notations and problems statement

The used notations throughout this paper and their definitions are presented in Table 2.

Table 2 Notations
Full size table

The integrated scheduling problem is formulated as a two-stage model. During the component production stage, the product components are processed and delivered in batches. Each semi-product manufacturer ensures that the completion time is minimized by solving a serial-batching scheduling problem, which is denoted as Q1. Then, during the assembly stage, the assembly manufacturer aims at minimizing the makespan under the constraints of the component finishing time and transportation, which is denoted as Q2. In the manufacturing system, the semi-product manufacturers first make decisions and then the assembly manufacturers will try to minimize the makespan based on their decisions. During the above scheduling period, the decisions concern: (1) how to group product components into batches for each semi-product manufacturer, (2) how to sequence the batches, (3) how to assign products to the assembly machines, and (4) how to sequence the products on each assembly machine. The decisions (1) and (2) are for the semi-product manufacturer, while the decisions (3) and (4) are for the assembly manufacturers. The joint decisions can improve the efficiency of the whole manufacturing system. The two-stage formulation is consistent with the service-oriented global manufacturing system, where different manufacturing service providers finish the finial products together and want to gain more profit through improving the efficiency.

The structure of the integrated scheduling problem is depicted in Fig. 2. We assume that there are \( N \) products \( \left\{ {P_{1} ,P_{2} , \ldots ,P_{I} , \ldots ,P_{N} } \right\} \) to be processed by \( g \) semi-product manufacturers \( \left\{ {M_{1} ,M_{2} , \ldots ,M_{m} , \ldots ,M_{g} } \right\} \) and \( G \) machines of an assembly manufacturer. There are \( g \) semi-product manufacturers processing different product components, and each of them is necessary for the final products, i.e., the \( m \)th product component must be processed by the \( m \)th semi-product manufacturer. Hence, each product consists of \( g \) components \( \left\{ {p_{I.1} ,p_{i,2} , \ldots ,p_{i,m} , \ldots ,p_{i,g} } \right\} \). During the production stage, the components are finished by the semi-product manufacturers. Each semi-product manufacturer has a single serial-batching machine. The machine capacity is denoted as \( c \), which means that the number of jobs in a batch cannot exceed \( c \). The setup time is required to start a new batch. Let \( B_{e.m} \) denote the \( e \)th batch in the \( m \) th semi-product manufacturer. The setup time is formulated as in Cheng et al. (2011):

$$ s_{e,m} = \theta T,\;e = 1,2, \ldots ,n_{m} ,\;m = 1,2, \ldots ,g. $$
(1)

where \( \theta \) is the deteriorating rate, \( T \) denotes the starting time, and \( n_{m} \) is the number of batches on the machine from the \( m \)th semi-product manufacturer. In addition, the sum-of-processing-times-based deterioration (Liu et al. 2013) is extended to serial-batching scheduling criteria. Denoting the normal processing time of the \( j \)th component on \( M_{m} \) as \( t_{\left[ j \right],m} \), the actual processing time of the \( j \)th component on \( M_{m} \) is formulated as follows:

$$\begin{aligned} & t_{\left[ j \right],m}^{A} = \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{\left[ j \right],m}, \\ &\qquad j = 1,2, \ldots ,N,\;m = 1,2, \ldots ,g,\;\mathop \sum \limits_{x = 1}^{0} t_{\left[ x \right],m}^{A} = 0. \end{aligned} $$
(2)
Fig. 2
figure 2

The integrated scheduling problem with production, transportation, and assembly

Full size image

After the production stage, the finished components are delivered to the assembly manufacturer and assembled into final products. The capacity limitation on the delivery is equal to that of the production machine. We assume that there are enough vehicles to deliver each batch as soon as it is finished in the production stage. The semi-product manufacturers are in different places, which results in different delivery times. We denote the delivery time between the \( m \)th semi-product manufacturer and the assembly manufacturer as \( D_{m} \), \( m = 1,2, \ldots ,g \). Then, for the assembly stage, each machine in the assembly manufacturer can only assemble one product at one time. Considering that human activities are of great significance in the assembly stage, we use the learning model proposed in Cheng et al. (2009) to formulate the actual assembly time of each product such that:

$$\begin{aligned} & a_{\left[ l \right],d}^{A} = \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{\left[ l \right],d} ,\\ & \quad\;\;\,\, l = 1,2, \ldots ,N_{d} ,\;d = 1,2, \ldots ,G,\;\mathop \sum \limits_{x = 1}^{0} \ln a_{\left[ x \right],d} = 0.\end{aligned} $$
(3)

where \( a_{\left[ l \right],d} \) denotes the normal processing time of the \( l \)th product on \( AM_{d} \) and \( \alpha < 0 \) is the learning index. In addition, the setup time for each product is formulated as:

$$ S_{\left[ l \right],d} = \delta T,\quad l = 1,2, \ldots ,N_{d} ,\;d = 1,2, \ldots ,G $$
(4)

where \( \delta \) is the deteriorating rate for the assembly process, \( T \) denotes the starting time, and \( N_{d} \) is the number of products in the \( d \)th assembly machine.

3 Structural properties and an optimal algorithm for Q1

In this section, we focus on the serial-batching scheduling problem in the production stage. Some structural properties are proposed, and an optimal rule is designed to schedule product components in each semi-product manufacturer. Moreover, the completion time of the product components is derived, which is very important for the decision making on the assembly stage.

Lemma 1

In an optimal schedule for a certain semi-product manufacturer, all product components are sorted in the non-decreasing order of the normal processing times.

Proof

Suppose that there are two adjacent product components \( p_{{I_{1} ,m}} \) and \( p_{{I_{2} ,m}} \) in the \( m \)th semi-product manufacturer, where \( I_{1} = 1,2, \ldots ,N \) and \( I_{2} = 1,2, \ldots ,N \), we consider two cases in this proof. One is that the two product components \( p_{{I_{1} ,m}} \) and \( p_{{I_{2} ,m}} \) are from the same batch, and the other is that they are from different batches. For the first case, we assume that there exist two schedules \( \pi = \Big\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{1} ,m}} , p_{{I_{2} ,m}} , \ldots }}_{{B_{e,m} }},W_{2} } \Big\} \) and \( \pi^{*} = \Big\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{2} ,m}} , p_{{I_{1} ,m}} , \ldots }}_{{B_{e,m} }},W_{2} } \Big\} \), where \( W_{1} \) and \( W_{2} \) are the partial sequences. Let \( S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) \) and \( j \) denote the starting time and the position of the product component \( p_{{I_{1} ,m}} \) in \( \pi \). Then, we can calculate the completion time of the product component \( p_{{I_{2} ,m}} \) in \( \pi \) as

$$ \begin{aligned} & C\left( {p_{{I_{2} ,m}} \left( \pi \right)} \right) \\ & = S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{1} ,m}} \\ & + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{1} ,m}} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{2} ,m}} = S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) \\ & + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right) \cdot \left( {t_{{I_{1} ,m}} + t_{{I_{2} ,m}} } \right) \\ & + \frac{{\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)}}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{{I_{1} ,m}} \cdot t_{{I_{2} ,m}} \\ \end{aligned} $$

Similarly, the completion time of the product component \( p_{{I_{1} ,m}} \) in \( \pi^{*} \) is

$$ C\left( {p_{{I_{1} ,m}} \left( {\pi^{*} } \right)} \right) = S\left( {p_{{I_{2} ,m}} \left( {\pi^{*} } \right)} \right) + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right) \cdot \left( {t_{{I_{1} ,m}} + t_{{I_{2} ,m}} } \right) + \frac{{\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)}}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{{I_{1} ,m}} \cdot t_{{I_{2} ,m}} . $$

Since \( S\left( {p_{{I_{2} ,m}} \left( {\pi^{*} } \right)} \right) = S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) \), we obtain \( C\left( {p_{{I_{2} ,m}} \left( \pi \right)} \right) = C\left( {p_{{I_{1} ,m}} \left( {\pi^{*} } \right)} \right) \).

For the second case, we take the similar expression as in the first case but define the two different schedules as \( \pi = \Big\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{1} ,m}} }}_{{B_{e,m} }},\underbrace {{p_{{I_{2} ,m}} , \ldots }}_{{B_{e + 1,m} }},W_{2} } \Big\} \) and \( \pi^{*} = \Big\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{2} ,m}} }}_{{B_{e,m} }},\underbrace {{p_{{I_{1} ,m}} , \ldots ,}}_{{B_{e + 1,m} }}W_{2} } \Big\} \).

Then, we derive

$$ \begin{aligned} & C\left( {p_{{I_{2} ,m}} \left( \pi \right)} \right) \\ & \quad = \left( {1 + \theta } \right)S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) + \left( {1 + \theta } \right)\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{1} ,m}} \\ & \quad \quad + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{1} ,m}} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{2} ,m}} = \left( {1 + \theta } \right)S\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) \\ & \quad \quad + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right) \cdot \left( {t_{{I_{1} ,m}} + t_{{I_{2} ,m}} } \right) + \frac{{\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)}}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }} \\ & \quad t_{{I_{1} ,m}} \cdot t_{{I_{2} ,m}} + \theta \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{1} ,m}} . \\ \end{aligned} $$

and

$$ \begin{aligned} & C\left( {p_{{I_{1} ,m}} \left( {\pi^{*} } \right)} \right) \\ & \quad = \left( {1 + \theta } \right)S\left( {p_{{I_{2} ,m}} \left( {\pi^{*} } \right)} \right) + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right) \cdot \left( {t_{{I_{1} ,m}} + t_{{I_{2} ,m}} } \right) \\ & \quad \quad + \frac{{\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)}}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{{I_{1} ,m}} \cdot t_{{I_{2} ,m}} \\ & \quad \quad + \theta \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{2} ,m}} . \\ \end{aligned} $$

Hence, we have \( C\left( {p_{{I_{2} ,m}} \left( \pi \right)} \right) - C\left( {p_{{I_{1} ,m}} \left( {\pi^{*} } \right)} \right) = \theta \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j - 1} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)\left( {t_{{I_{1} ,m}} - t_{{I_{2} ,m}} } \right) \).

Combining the two cases, it can be derived \( C\left( {p_{{I_{2} ,m}} \left( \pi \right)} \right) \le C\left( {p_{{I_{1} ,m}} \left( {\pi^{*} } \right)} \right) \) when \( t_{{I_{1} ,m}} \le t_{{I_{2} ,m}} \). Thus, this lemma is proved. □

Lemma 2

In an optimal schedule for a certain semi-product manufacturer, all batches contain \( c \) product components except for the first batch in each semi-product manufacturer.

Proof

Let \( B_{e,g} \) and \( B_{e + 1,g} \) be two adjacent batches, where \( e = 1, \cdots ,n_{m} - 1 \). We assume that the number of product components in \( B_{e + 1,g} \) is less than \( c \), the last two product components in \( B_{e,g} \) are \( p_{{I_{1} ,m}} \) and \( p_{{I_{2} ,m}} \), and the first product component in \( B_{e + 1,g} \) is \( p_{{I_{3} ,m}} \), i.e., \( \pi = \Bigg\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{1} ,m}} ,p_{{I_{2} ,m}} ,}}_{{B_{e,m} }}\underbrace {{p_{{I_{3} ,m}} \ldots }}_{{B_{e + 1,m} }},W_{2} } \Bigg\} \). Then, we obtain a new schedule \( \pi^{ *} \) by moving the product component \( p_{{I_{2} ,m}} \) from \( B_{e,m} \) to \( B_{e + 1,m} \) such that \( \pi^{ *} = \left\{ {W_{1} ,\underbrace {{ \ldots ,p_{{I_{1} ,m}} }}_{{B_{e,m} }}\underbrace {{,p_{{I_{2} ,m}} ,p_{{I_{3} ,m}} \ldots }}_{{B_{e + 1,m} }},W_{2} } \right\} \). Suppose the \( p_{{I_{1} ,m}} \) is in the \( j \)th position, the completion times of \( p_{{I_{2} ,m}} \) in \( \pi \) and \( \pi^{ *} \) are calculated as \( S\left( {p_{{I_{3} ,m}} \left( \pi \right)} \right) = \left( {1 + \theta } \right)C\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) + \left( {1 + \theta } \right)\left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{2} ,m}} \) and \( S\left( {p_{{I_{3} ,m}} \left( {\pi^{ *} } \right)} \right) = \left( {1 + \theta } \right)C\left( {p_{{I_{1} ,m}} \left( \pi \right)} \right) + \left( {1 + \frac{{\mathop \sum \nolimits_{x = 1}^{j} t_{\left[ x \right],m}^{A} }}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}} \right)t_{{I_{2} ,m}} \). Then, since the other sequences are the same for the two schedules, it is easy to obtain \( C_{max}^{m} \left( \pi \right) > C_{max}^{m} \left( {\pi^{ *} } \right) \). Thus, it can be concluded that this lemma holds. □

Then, based on Lemmas 1 and 2, we develop the following schedule algorithm on product components sequencing, batching, and batch sequencing.

Algorithm 1

Step 1. For each semi-product manufacturer, sort the product components in the non-decreasing order of the normal processing times.

Step 2. If \( N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil < 0 \), then, group the first \( N - c \cdot \left( {\left\lceil {\frac{N}{c}} \right\rceil - 1} \right) \) product components into a batch and remove them from the list.

Step 3. Group the first \( c \) product components into a new batch and remove them from the list.

Step 4. Repeat Step 3 until the job list is empty.

Step 5. Process the batches in the generated order and process the product components in the non-decreasing order of the normal processing times.

Since the computational complexity of step 1 and the steps 2–5 is \( O(N\log N) \) and \( O\left( N \right) \), respectively, the total complexity of Algorithm 1 is \( O\left( {N\log N} \right) \). Based on Lemmas 1 and 2, we know that Algorithm 1 can obtain the optimal schedule for each semi-product manufacturer.

Lemma 3

For the problem Q1, the completion time of each semi-product manufacturer is:

$$ \begin{aligned} & C_{ \hbox{max} }^{m} = \mathop \sum \limits_{x = 1}^{N} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{N} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{N} t_{\left[ x \right],m} \\ & \quad - \mathop \sum \limits_{x = 1}^{{f\left( {\left\lceil {\frac{N}{c}} \right\rceil - 1} \right)}} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{N} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) + \mathop \sum \limits_{x = 1}^{{f\left( {\left\lceil {\frac{N}{c}} \right\rceil - 1} \right)}} t_{\left[ x \right],m} \\ & \quad + \mathop \sum \limits_{z = 1}^{{\left\lceil {N/c} \right\rceil - 1}} \left( {1 + \theta } \right)^{{\left\lceil {N/c} \right\rceil - z}} \left[ {\mathop \sum \limits_{x = 1}^{f\left( z \right)} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{f\left( z \right)} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{f\left( z \right)} t_{\left[ x \right],m} } \right. \\ & \left. {\quad - \mathop \sum \limits_{x = 1}^{{f\left( {z - 1} \right)}} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{{f\left( {z - 1} \right)}} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) + \mathop \sum \limits_{x = 1}^{{f\left( {z - 1} \right)}} t_{\left[ x \right],m} } \right] \\ \end{aligned} $$
(5)

where

$$ f\left( z \right) = \left\{ {\begin{array}{*{20}l} {N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil + z \cdot c,N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil < 0,} \hfill & {z > 0} \hfill \\ {zc,} \hfill & {N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil = 0,z > 0} \hfill \\ {0,} \hfill & {z = 0.} \hfill \\ \end{array} } \right. $$

Proof

Given an optimal schedule in each semi-product manufacturer such as \( \pi = \left\{ {B_{1,m} ,B_{2,m} , \ldots ,B_{{\left\lceil {\frac{N}{c}} \right\rceil ,m}} } \right\} \), we can derive the number of jobs in each batch based on Lemmas 1 and 2, e.g., the number of jobs in \( \left| {B_{e,m} } \right| \) is \( \left| {B_{e,m} } \right| = \left\{ {\begin{array}{*{20}l} {N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil + c,N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil < 0,} \hfill & {e = 1} \hfill \\ {c,} \hfill & {\text{other}} \hfill \\ \end{array} } \right. \). Hence, it can be obtained that the total number of jobs in the first \( e > 0 \) batches is \( \sum\nolimits_{x = 1}^{e} {\left| {B_{e,m} } \right| = f\left( e \right) = } \left\{ {\begin{array}{*{20}l} {N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil + e \cdot c,} \hfill & {N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil < 0} \hfill \\ {ec,} \hfill & { N - c \cdot \left\lceil {\frac{N}{c}} \right\rceil = 0} \hfill \\ \end{array} } \right. \). Then, we can prove this lemma using mathematical induction. First, for \( e = 1 \), we have

$$ C\left( {B_{1,m} } \right) = \mathop \sum \limits_{x = 1}^{f\left( 1 \right)} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{f\left( 1 \right)} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{f\left( 1 \right)} t_{\left[ x \right],m} . $$

Assume that we have:

$$ \begin{aligned} C\left( {B_{e,m} } \right) & = \sum\limits_{x = 1}^{f\left( e \right)} {t_{\left[ x \right],m} } \prod\limits_{y = 1}^{f\left( e \right)} {\left( {1 + \frac{1}{{\sum\nolimits_{x = 1}^{N} {t_{\left[ x \right],m} } }}t_{\left[ y \right],m} } \right)} - \sum\limits_{x = 1}^{f\left( e \right)} {t_{\left[ x \right],m} } \\ & \quad - \sum\limits_{x = 1}^{{f\left( {e - 1} \right)}} {t_{\left[ x \right],m} } \prod\limits_{y = 1}^{N} {\left( {1 + \frac{1}{{\sum\nolimits_{x = 1}^{N} {t_{\left[ x \right],m} } }}t_{\left[ y \right],m} } \right)} + \sum\limits_{x = 1}^{{f\left( {e - 1} \right)}} {t_{\left[ x \right],m} } \\ & \quad + \sum\limits_{z = 1}^{e - 1} {\left( {1 + \theta } \right)^{{\left\lceil {N/c} \right\rceil - z}} } \left[ {\sum\limits_{x = 1}^{f\left( z \right)} {t_{\left[ x \right],m} } \prod\limits_{y = 1}^{f\left( z \right)} {\left( {1 + \frac{1}{{\sum\nolimits_{x = 1}^{N} {t_{\left[ x \right],m} } }}t_{\left[ y \right],m} } \right)} - \sum\limits_{x = 1}^{f\left( z \right)} {t_{\left[ x \right],m} } } \right. \\ & \left. { - \sum\limits_{x = 1}^{{f\left( {z - 1} \right)}} {t_{\left[ x \right],m} } \prod\limits_{y = 1}^{{f\left( {z - 1} \right)}} {\left( {1 + \frac{1}{{\sum\nolimits_{x = 1}^{N} {t_{\left[ x \right],m} } }}t_{\left[ y \right],m} } \right)} + \sum\limits_{x = 1}^{{f\left( {z - 1} \right)}} {t_{\left[ x \right],m} } } \right] \\ \end{aligned} $$
(6)

for the batch \( B_{e,m} \). Then, for the batch \( B_{e + 1,m} \), we derive its completion time as

$$ \begin{aligned} C\left( {B_{e + 1,m} } \right) & = \theta C\left( {B_{e,m} } \right) + C\left( {B_{e,m} } \right) + \mathop \sum \limits_{x = 1}^{{f\left( {e + 1} \right)}} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{{f\left( {e + 1} \right)}} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{{f\left( {e + 1} \right)}} t_{\left[ x \right],m} \\ & \quad - \left[ {\mathop \sum \limits_{x = 1}^{f\left( e \right)} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{f\left( e \right)} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{f\left( e \right)} t_{\left[ x \right],m} } \right] \\ & = \mathop \sum \limits_{x = 1}^{{f\left( {e + 1} \right)}} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{{f\left( {e + 1} \right)}} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{{f\left( {e + 1} \right)}} t_{\left[ x \right],m} \\ & \quad - \mathop \sum \limits_{x = 1}^{f\left( e \right)} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{N} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) + \mathop \sum \limits_{x = 1}^{f\left( e \right)} t_{\left[ x \right],m} \\ & \quad + \mathop \sum \limits_{z = 1}^{e} \left( {1 + \theta } \right)^{{\left\lceil {\frac{N}{c}} \right\rceil - z}} \left[ {\mathop \sum \limits_{x = 1}^{f\left( z \right)} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{f\left( z \right)} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) - \mathop \sum \limits_{x = 1}^{f\left( z \right)} t_{\left[ x \right],m} } \right. \\ & \quad \left. { - \mathop \sum \limits_{x = 1}^{{f\left( {z - 1} \right)}} t_{\left[ x \right],m} \mathop \prod \limits_{y = 1}^{{f\left( {z - 1} \right)}} \left( {1 + \frac{1}{{\mathop \sum \nolimits_{x = 1}^{N} t_{\left[ x \right],m} }}t_{\left[ y \right],m} } \right) + \mathop \sum \limits_{x = 1}^{{f\left( {z - 1} \right)}} t_{\left[ x \right],m} } \right]. \\ \end{aligned} $$

Thus, Eq. 6 also holds for the batch \( B_{e + 1,m} \). Combing the above results, we can conclude that this lemma holds. □

4 Structural properties and a local search strategy for Q2

Based on the results obtained in Sect. 3, the available time of each product in the assembly stage is derived. Further, under the case where products have been assigned to assembly machines, we proposed a local search strategy to improve the solution quality.

Lemma 4

For the problem Q2, the available time of each product is

$$ R_{I} = \mathop {\hbox{max} }\limits_{1 \le m \le g} \left\{ {X_{i,e,m} C\left( {B_{e,m} } \right) + D_{m} } \right\} $$
(7)

where \( X_{i,e,m} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {if p_{i,m} is assigned to B_{e,m} } \hfill \\ {0,} \hfill & {else} \hfill \\ \end{array} } \right. \).

Lemma 5

Let \( F\left( \lambda \right) = \left( {1 + \delta } \right)\left( {\lambda - 1} \right) + \left( {1 + c_{0} ln\lambda + c_{0} x} \right)^{\alpha } - \lambda \left( {1 + c_{0} x} \right)^{\alpha } \), then \( F\left( \lambda \right) \ge 0 \) for \( \delta \ge 0 \), \( \lambda \ge 1 \), \( 0 < c_{0} < 1 \),\( x > 1 \), and \( \alpha < 0 \).

Proof

The lemmas can be easily proved by analyzing the first derivative and the second derivative of \( F\left( \lambda \right) \) as the proof of Lemma 3 in Cheng et al. (2009), so we omit it here.

Lemma 6

For the problem Q2, given the assignment of products, if there exist two adjacent products with \( R_{{I_{1} }} \le R_{{I_{2} }} \) and \( a_{{I_{1} }} \le a_{{I_{2} }} \) , then the \( P_{{I_{1} }} \) should be processed preceded by \( P_{{I_{2} }} \) in an optimal schedule.

Proof

Suppose that \( \varphi = \left\{ {E_{1} ,P_{{I_{1} }} ,P_{{I_{2} }} ,E_{2} } \right\} \) and \( \varphi^{*} = \left\{ {E_{1} ,P_{{I_{2} }} ,P_{{I_{1} }} ,E_{2} } \right\} \) are two product schedules, where \( E_{1} \) and \( E_{2} \) are partial product sequences, \( R_{{I_{1} }} \le R_{{I_{2} }} \), and \( a_{{I_{1} }} \le a_{{I_{2} }} \). We assume that \( \varphi^{*} \) is an optimal schedule for the Q2 given the assignment of products. In addition, the position of \( P_{{I_{1} }} \) in \( \varphi \) is \( l \). Denoting the completion time of the last product in \( E_{1} \) as \( A\left( {E_{1} } \right) \), the completion time of \( P_{{I_{1} }} \) and \( P_{{I_{2} }} \) in \( \varphi \) is

$$ \begin{aligned} A\left( {P_{{I_{1} }} \left( \varphi \right)} \right) & = \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{1} ,d}} + \delta \hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{1} }} } \right\} + \hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{1} }} } \right\} \\ & = \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{1} ,d}} + \left( {\delta + 1} \right)\hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{1} }} } \right\} \\ \end{aligned} $$

and:

$$ \begin{aligned} & A\left( {P_{{I_{2} }} \left( \varphi \right)} \right) = \left( {\delta + 1} \right)\hbox{max} \left\{ {A\left( {P_{{I_{1} }} \left( \varphi \right)} \right),R_{{I_{2} }} } \right\} + \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} + \ln a_{{I_{1} ,d}} } \right)^{\alpha } a_{{I_{2} ,d}} \\ & = \left( {\delta + 1} \right)\hbox{max} \left\{ {\left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{1} ,d}} + \left( {\delta + 1} \right)A\left( {E_{1} } \right),\left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{1} ,d}} } \right. \\ & \quad \left. { + \left( {\delta + 1} \right)R_{{I_{1} }} ,R_{{I_{2} }} } \right\} + \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} + \ln a_{{I_{1} ,d}} } \right)^{\alpha } a_{{I_{2} ,d}} . \\ \end{aligned} $$
(8)

Then, for the schedule \( \varphi^{*} \), we also calculate the completion time of \( P_{{I_{1} }} \) and \( P_{{I_{2} }} \) as follows:

$$ \begin{aligned} A\left( {P_{{I_{2} }} \left( {\varphi^{*} } \right)} \right) = & \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{2} ,d}} + \delta \hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{2} }} } \right\} + \hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{2} }} } \right\} \\ = & \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{2} ,d}} + \left( {\delta + 1} \right)\hbox{max} \left\{ {A\left( {E_{1} } \right),R_{{I_{2} }} } \right\} \\ \end{aligned} $$

and:

$$ \begin{aligned} & A\left( {P_{{I_{1} }} \left( {\varphi^{*} } \right)} \right) = \left( {\delta + 1} \right)\hbox{max} \left\{ {A\left( {P_{{I_{2} }} \left( {\varphi^{*} } \right)} \right),R_{{I_{1} }} } \right\} + \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} + \ln a_{{I_{2} ,d}} } \right)^{\alpha } a_{{I_{1} ,d}} \\ & = \left( {\delta + 1} \right)\hbox{max} \{ \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{2} ,d}} + \left( {\delta + 1} \right)A\left( {E_{1} } \right), \\ & \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{2} ,d}} + \left( {\delta + 1} \right)R_{{I_{2} }} ,R_{{I_{1} }} \} \\ & + \left( {1 + \mathop \sum \limits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} + \ln a_{{I_{2} ,d}} } \right)^{\alpha } a_{{I_{1} ,d}} . \\ \end{aligned} $$
(9)

Set \( \lambda = \frac{{a_{{I_{2} ,d}} }}{{a_{{I_{1} ,d}} }} \), \( c_{0} = \frac{1}{{1 + \mathop \sum \nolimits_{x = 1}^{l - 1} \ln a_{\left[ x \right],d} }} \), and \( x = \ln a_{{I_{1} ,d}} \); then, based on Lemma 5, we obtain

$$ \begin{aligned} & \left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} + \ln a_{{I_{2} ,d}} } \right)^{\alpha } a_{{I_{1} ,d}} + \left( {\delta + 1} \right)\left[ {\left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{2} ,d}} } \right] \\ & - \left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} + \ln a_{{I_{1} ,d}} } \right)^{\alpha } a_{{I_{2} ,d}} - \left( {\delta + 1} \right)\left[ {\left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} } \right)^{\alpha } a_{{I_{1} ,d}} } \right] \\ & = a_{{I_{1} ,d}} \left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} } \right)^{\alpha } [\left( {\delta + 1} \right)\left( {\frac{{a_{{I_{2} ,d}} }}{{a_{{I_{1} ,d}} }} - 1} \right) \\ & + \left( {1 + \frac{1}{{1 + \sum\nolimits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} }}\ln \frac{{a_{{I_{2} ,d}} }}{{a_{{I_{1} ,d}} }} + \frac{1}{{1 + \sum\nolimits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} }}\ln a_{{I_{1} ,d}} } \right)^{\alpha } \\ & - \frac{{a_{{I_{2} ,d}} }}{{a_{{I_{1} ,d}} }}\left( {1 + \frac{1}{{1 + \sum\nolimits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} }}\ln a_{{I_{1} ,d}} } \right)^{\alpha } ] \\ & = a_{{I_{1} ,d}} \left( {1 + \sum\limits_{x = 1}^{l - 1} {\ln } a_{\left[ x \right],d} } \right)^{\alpha } \left[ {\left( {\delta + 1} \right)\left( {\lambda - 1} \right) + \left( {1 + c_{0} \ln \lambda + c_{0} x} \right)^{\alpha } - \lambda \left( {1 + c_{0} x} \right)^{\alpha } } \right] \ge 0. \\ \end{aligned} $$

Hence, we have:

The first term in Eq. (9)\( \ge \) the first term in Eq. (8);

The second term in Eq. (9)\( \ge \) the second term in Eq. (8);

The second term in Eq. (9)\( \ge \) the third term in Eq. (8).

Thus, \( A\left( {P_{{I_{1} }} \left( {\varphi^{*} } \right)} \right) \ge A\left( {P_{{I_{2} }} \left( \varphi \right)} \right) \), which conflicts with the assumption. The proof is completed.

Let \( R_{\left[ l \right],d} \) denote the available time of the \( l \)th product in \( AM_{d} \). Based on Lemma 6, we design the following algorithm to improve the solution quality in the assembly stage.

Algorithm 2

Step 1. Set \( l = 1 \).

Step 2. If \( R_{\left[ l \right],d} \ge R_{{\left[ {l + 1} \right],d}} \) and \( a_{\left[ l \right],d} \ge a_{{\left[ {l + 1} \right],d}} \), then, go to step 3; else, go to step 5.

Step 3. If \( R_{\left[ l \right],d} = R_{{\left[ {l + 1} \right],d}} \) and \( a_{\left[ l \right],d} = a_{{\left[ {l + 1} \right],d}} \), then, go to step 5; else, swap the products in the \( l \)th and \( \left( {l + 1} \right) \)th positions and go to step 4.

Step 4. If \( l = 1 \), then, go to step 5; else, set \( l = l - 1 \) and go to step 2.

Step 5. Set \( l = 1 + l \). If \( l < N_{d} - 1 \), then, go to Step 2; else, end the algorithm.

Based on Lemma 6, it is known that Algorithm 2 can improve the solution quality and eliminate some inappropriate solutions. The computation complexity will not exceed \( O(l^{2} \)).

5 LIMA-VNS metaheuristic

If \( R_{I} = 0 \) and \( \alpha = 0 \), the studied problem is reduced to the NP-hard problem \( P||A_{ \hbox{max} } \) (Coffman et al. 1978). Then, we can infer that the studied problem is also NP-hard. Hence, we develop a metaheuristic in this section to solve the problem in a reasonable time. The VNS is a very effective metaheuristic proposed by Mladenović and Hansen (1997). It aims at achieving an overall optimization in the solution space through systematically exploring different neighborhood structures. There are three significant principles for the VNS: the first principle is that a local optimal solution in one neighborhood structure may not be the optimal solution for another one; the second principle is that an overall optimal solution is the optimal solution for any kinds of neighborhood structures; and the last principle states that the local optimal solutions are close to each other, which is summarized in many experiments. VNS has shown a good performance in many complex scheduling problems (Bouffard and Ferland 2007, Wen et al. 2011, Zhang et al. 2018). To increase the diversity of solutions, other metaheuristics such as genetic algorithms and simulated annealing are integrated into the framework of VNS. However, Mladenović et al. (2016) suggested that integrating too many operations into VNS may not lead to better results. On the contrary, “less can yield more” exists in many problems. Based on this idea, we have designed a LIMA-VNS for an assembly scheduling problem with deteriorating and learning effects. We will first introduce the encoding scheme for the scheduling problem. Then, the procedure for generating the initial solution is described. Next, we present a simple and effective neighborhood for the scheduling problem, and the nested version of the neighborhood consists of the neighborhoods of the LIMA-VNS. This neighborhood composition is different from much existing literature which integrates several types of complex neighborhoods or heuristics into the VNS algorithm, such as in Roshanaei et al. (2009). Finally, we give the framework of the whole solution procedure. The neighborhood composition and framework of the algorithm both reflect the “less can yield more” mentioned above, obtaining better results with the most compact neighborhood and algorithm structure.

5.1 Solution representation

The metaheuristic LIMA-VNS is introduced to assign products to the assembly machines and to find an approximately optimal schedule for each machine. Thus, we use a \( \left( {N + G - 1} \right) \)-dimensional vector which is comprised of integers between 1 and \( N + G - 1 \) to express a solution in the assembly stage. The numbers between 1 and \( N \) denote products, while the numbers between \( N + 1 \) and \( N + G - 1 \) are flags which divide the products into \( G \) sets. The \( G \) sets will be assigned to the \( G \) assembly machines in turn. Hence, each number between 1 and \( N + G - 1 \) must appear only once in each solution. A problem instance with 6 products and 3 machines is used to describe the solution representation in Fig. 3.

Fig. 3
figure 3

The solution representation for a problem instance

Full size image

For the given solution vector \( V = \left\{ {1,7,3,2,6,5,8,4} \right\} \), 7 and 8 are the two flags while 1–6 denote the 6 products. The product on the left of 7 is assigned to the assembly machine \( {\text{AM}}_{1} \). The product \( P_{4} \) is processed on the assembly machine \( {\text{AM}}_{3} \). Products \( P_{3} \), \( P_{2} \), \( P_{6} \), and \( P_{5} \) are assigned to the assembly machine \( {\text{AM}}_{2} \) and processed in the order \( P_{3} \to P_{2} \to P_{6} \to P_{5} \). The designed solution vector in this work specifies not only to which assembly machines the products are assigned ut also the processing order of the products on the assembly machines. Compared with continuous coding, this kind of discrete coding can better take advantage of VNS, which does not depend on complex update formulae, but relies on simple and diverse neighborhood structures. Compared with high-dimensional machine-assigned codes, this code has lower spatial complexity.

5.2 Initial solution generation

VNS is a single trajectory metaheuristic in the same way as simulated annealing and Tabu search (BoussaïD et al. 2013), which indicates that a single solution \( V \) is kept during the whole search process. Hence, the quality of the initial solution is significant for the performance of the metaheuristic. To obtain a good initial solution for LIMA-VNS, we first randomly generate a set which contains \( x_{ \hbox{max} } \) solutions, and Algorithm 2 will then be used to improve each solution. Finally, the best solution among the improved solutions will be selected as the initial solution of the metaheuristic. The procedure for generating the initial solution is described in Algorithm 3 as follows:

Algorithm 3

Step 1. Set \( x = 1 \).

Step 2. Set \( V_{x} = \left\{ {v_{1} ,v_{2} , \ldots ,v_{N + G - 1} } \right\} \), \( X = \left\{ {1,2, \ldots ,N + G - 1} \right\} \), and \( y = 1 \).

Step 3. Set \( rand = random\left( {1,N + G - 1} \right) \), \( v_{y} = X\left[ {rand} \right] \).

Step 4. If \( rand < N + G - 1 \), then, set \( X\left[ {rand} \right] = X\left[ {rand + 1} \right] \) and go to step 6; else, go to step 5.

Step 5. If \( rand > 1 \), then, set \( X\left[ {rand} \right] = X\left[ {rand - 1} \right] \) and go to step 6; else, output \( V_{x} \) and end the algorithm.

Step 6. Set \( y = y + 1 \). If \( y > N + G - 1 \), then, go to step 7; else, go to step 3.

Step 7. Perform Algorithm-2 on \( V_{x} \). Set \( x = x + 1 \). If \( x > x_{max} \), then, output the best one among the \( x_{max} \) solutions and end the algorithm; else, go to step 2.

In Algorithm 3, steps 3–6 can generate a feasible solution where each number between 1 and \( N + G - 1 \) appears once. Additionally, Algorithm 2 is able to improve the solution quality without generating infeasible solutions.

5.3 Neighborhood structures

The swap local search operator generates a new solution through an interchange of solution attributes (Mladenović and Hansen 1997), which is regarded as a very effective neighborhood structure in VNS. We modify this classical local search operator according to the nature of our investigated problem. Let \( x \) and \( y \) denote two integer numbers; for an original solution \( V = \left\{ {v_{1} ,v_{2} , \ldots ,v_{N + G - 1} } \right\} \), the steps of the modified swap local search operator are shown as follows:

Algorithm 4

Step 1. Set \( z = random\left( {1,N + G - 1} \right) \) and \( y = random\left( {1,N + G - 1} \right) \).

Step 2. If \( z = y \), then, go back to step 1; else, go to step 3.

Step 3. If \( v_{z} > N \& \& v_{y} > N \), then, go back to step 1; else, go to step 4.

Step 4. Swap the two attributes such as \( v_{z} \) and \( v_{y} \) in \( V \) to get the new solution \( V^{\prime} \). Output \( V^{\prime} \).

For the presented encoding scheme in Sect. 5.1, any interchange of two attributes which are both larger than \( N \) will not change the final schedule. Hence, compared to the general swap operator, the modified swap operator in this work ensures that the output solution \( V^{\prime} \) is different from the original solution. Then, the metaheuristic can avoid unnecessary decoding and waste of computational time. Using \( {\text{NEI}}_{\omega } \) to denote \( \omega \) execution of the modified swap operator, we build a set of the neighborhood structures for the LIMA-VNS.

5.4 The framework of the solution procedure

Based on Algorithms 1–4, we have designed a LIMA-VNS and three modifications are made according to the nature of the investigated problem and our encoding scheme. To improve diversification searching, the first modification is to realize the output of different schedules for the local search operator. To improve the quality of the neighborhood solutions, the second modification is the designing of Algorithm 2 based on structural properties. The last modification is that we give an initial solution generation algorithm based on the encoding scheme in this paper, which can output a feasible solution of good quality. Integrating too many other heuristics into VNS usually increases the number of decodes. The decoding process takes a lot of time, especially for complex scheduling problems such as the integrated scheduling problem in this work. Hence, these complex algorithms often require a lot of computing time and violate the needs of the enterprises. In our proposed algorithm, the evaluation of solution quality is only performed once in each iteration and the designed neighborhood structure is concise and efficient, which means that we use fewer procedures to obtain better results. That is the so-called “less is more algorithm.” The pseudocode of the whole solution procedure for the investigated problem is given as follows:

The pseudocode of the LIMA-VNS

Step 1.

Perform Algorithm 1 to obtain the available time of each product

Step 2.

Perform Algorithm 3 to obtain the initial solution. Set \( \omega = 1 \) and \( it = 0 \)

Step 3.

Select a neighborhood solution \( V^{{\prime }} \) from the \( {\text{NEI}}_{\omega } \) of \( V \)

Step 4.

Apply Algorithm 2 for \( V^{{\prime }} \), obtaining \( V^{{\prime \prime }} \)

Step 5.

If \( A_{ \hbox{max} } \left( {V^{{\prime \prime }} } \right) < A_{ \hbox{max} } \left( V \right) \), then set \( \omega = 1 \) and \( V = V^{{\prime \prime }} \), else set \( \omega = \omega + 1 \)

Step 6.

If \( \omega > \omega_{max} \), then set \( \omega = 1 \)

Step 7.

Set \( it = running time of the algorithm \)

Step 8.

If \( it \le itmax \), then go to step 3, else go to step 9

Step 9.

Output \( V \)

Costa et al. (2017) stated that the VNS metaheuristic based on a unique neighborhood structure can be very effective and provided the less is more approach (LIMA) on metaheuristic design. In this paper, the modified swap local search operator is regarded as the so-called unique neighborhood structure and we apply it in our implementation of a LIMA-VNS metaheuristic.

6 Computational experiments

In this section, we give the computational results of the developed VNS approach on the proposed scheduling problem and a comparison with other different metaheuristics. The selected metaheuristics in the comparative experiments have shown good performances on various types of scheduling problems, including VNS_R (Roshanaei et al. 2009), SA_C (Chen et al. 2017), and TS_E (El-Yaakoubi et al. 2017). The algorithms were coded in C++ language on an Intel Core 7-6700 with 16 G RAM, running Windows 7.

Algorithms 1 and 2 are used in all the metaheuristics which are compared by measuring the relative percentage deviation (RPD) between the reported makespan and the best-known makespan. The RPD is calculated as:

$$ {\text{RPD}}_{\text{alg}} = \frac{{A_{ \hbox{max} } \left( {\text{alg}} \right) - A_{ \hbox{max} } \left( {\text{best}} \right)}}{{A_{ \hbox{max} } \left( {\text{best}} \right)}} $$
(10)

where \( A_{ \hbox{max} } \left( {\text{alg}} \right) \) is the makespan obtained by the metaheuristic \( {\text{alg}} \) while \( A_{ \hbox{max} } \left( {\text{best}} \right) \) denotes the best-known solution. Since the objective is to minimize the makespan, a smaller RPD means a better result. For each problem instance, 20 replications are operated for all the metaheuristics. Table 3 gives a summary of the attributes and levels of the generated instances. Since our problem has not been considered before, we surveyed real-world equipment manufacturing companies to obtain the data for the complete experiments. In order to get reasonable experimental data, we also refer to the literature related to this article in recent years. For example, based on existing works such as Roshanaei et al. (2009) and Ahmadizar and Farhadi (2015), the deteriorating rates are in \( U\left[ {0.01,0.1} \right] \) while the normal processing times are in \( U\left[ {1,10} \right] \). Based on the relationship between processing time and transportation time, we set the delivery time in \( U\left[ {1,5} \right] \). In real-world manufacturing, the assembly processing time is more fixed and longer than the component production time. Hence, we set the normal processing time of the products as \( U\left[ {5,10} \right] \). Based on the levels of the attributes \( N \), \( g \), and \( G \), 27 problem instances are generated. We use the \( {\text{PMA}}\left( {x,y,z} \right) \) to denote the instance with \( x \) products, \( y \) semi-product manufacturers, and \( z \) assembly machines.

Table 3 Attributes and levels
Full size table

In the experiment, we find that the metaheuristics converge to a good result in 50 s, even for the problem instance of the largest scale such as \( {\text{PMA}}\left( {150,9,6} \right) \), which is shown in Fig. 4. Hence, we determine that each metaheuristic stops iterating after 50 s for each problem instance to achieve a fair comparison. In addition, in Fig. 4, LIMA-VNS also shows an advantage in convergence speed over the other three metaheuristics. Table 4 reports the summary of the results for the metaheuristics in 27 problem instances. The average objective value (Ave), the relative percentage deviation (RPD), and the variance (VAR) measured over the derived were calculated for each problem instance. For some small-scale experiments, such as \( {\text{PMA}}\left( {50,3,2} \right) \) and \( {\text{PMA}}\left( {50,3,4} \right) \), the other three metaheuristics may perform as well as LIMA-VNS. However, for most of the problem instances, average objective values and standard deviations obtained by LIMA-VNS are much smaller than those obtained by others, especially for the large-scale problem instances, e.g., \( {\text{PMA}}\left( {150,3,4} \right) \) and \( {\text{PMA}}\left( {150,9,4} \right) \). From Table 4, we can conclude that LIMA-VNS results in the best solution of Ave, VAR, and RPD among the four metaheuristics. From Fig. 5, we can see that solutions obtained by LIMA-VNS are gathered in the lower left corner of the coordinate system. However, for VNS_R, SA_C, and TS_E, the distribution of points on the graph is more dispersed compared to LIMA-VNS. Hence, it is shown that the designed LIMA-VNS can solve the problem stably. Based on the above computational experiment, we can infer that the LIMA-VNS has the best performance in converge speed, solution quality, and robustness. From the results of the experiment, we can summarize the contribution of the proposed method to real-world production. First, the proposed intelligent scheduling algorithm is easy to implement and can effectively improve the scientific nature of decision-making. Second, our algorithm can produce better results in a given time, that is, the application of the algorithm can reduce production time, thereby reducing the production and operating costs of the manufacturing companies. Moreover, timely delivery will increase user satisfaction and loyalty, thus providing long-term benefits for the enterprise. Finally, the LIMA-VNS is versatile and can solve other optimization decision problems for enterprises.

Fig. 4
figure 4

The converge curves of the metaheuristics over time on problem \( {\text{PMA}}\left( {150,9,6} \right) \)

Full size image
Table 4 Summary of results for all instances
Full size table
Fig. 5
figure 5

Plots of distances between solutions in each replication and the best-known solution

Full size image

7 Conclusion

Intelligent decision-making in complex product manufacturing systems is important for the realization of smart manufacturing. This paper investigates a coordinated production, delivery, and assembly scheduling problem with a deteriorating effect and a learning effect. Through the discussion of the problem characteristics, we propose the structural properties for the serial-batching scheduling problem and the assembly scheduling problem under the constraints of component finishing time and transportation, respectively. For the serial-batching scheduling problem, an optimization scheduling rule has been developed to solve the problem in polynomial time. For the assembly scheduling problem, an improvement strategy has been proposed based on the structural properties. Since the problem is NP-hard, we have designed a LIMA-VNS to find an approximately optimal solution in a reasonable time. To validate the performance of the designed LIMA-VNS, we compare it with other three metaheuristics from the latest literature which includes VNS_R, SA_C, and TS_E. Via computational experiments, we show that our approach finds the best solutions within a given time, especially for large-scale problems. In this paper, the designed coding scheme, neighborhood structures, and the metaheuristic are effective and easy to implement Those methods can be used in real-life manufacturing to increase productivity, which in turn will improve the competitiveness of all participants in the global manufacturing system.

There are some topics worthy of consideration in our future work. On a theoretical level, one important future research direction would be to model the multistage problems for the coordinating manufacturing. Another potential direction would be to extend the LIMA-VNS to further different optimization problems with effective neighborhood structures. On a practical level, we would consider the different requests of the manufacturers, such as cost minimization, lean production and design, more effective VNS, and heuristic algorithms to improve the manufacturing efficiency.