Type-1 Robotic Assembly Line Balancing Problem That Considers Energy Consumption and Cross-Station Design

Abstract

Robotic assembly lines are widely applied to mass production because of their adaptability and versatility. As we know, using robots will lead to energy-consumption and pollution problems, which has been a hot-button topic in recent years. In this paper, we consider an assembly line balancing problem with minimizing the number of workstations as the primary objective and minimizing energy consumption as the secondary objective. Further, we propose a novel mixed integer linear programming (MILP) model considering a realistic production process design—cross-station task, which is an important contribution of our paper. The “cross-station task” design has already been applied to practice but rarely studied academically in type-1 RALBP. A simulated annealing algorithm is developed, which incorporates a restart mechanism and an improvement strategy. Computational tests demonstrate that the proposed algorithm is superior to two other classic algorithms, which are the particle swarm algorithm and late acceptance hill-climbing algorithm.

1. Introduction

Assembly lines are widely utilized in mass production, such as automobiles and household appliances. Robots have gained appeal with line designers as a result of advances in manufacturing technology and the quest for production efficiency. Assembly line with robots is referred to as the robotic assembly line. Compared with human workers, robots can process tasks quickly and accurately without having to worry about undue fatigue. Further, a robot with multiple arms is also more adaptable and capable of processing a variety of tasks [1]. However, the utilization of robots will consume energy and create pollution problems. Fysikopoulos et al. [2] pointed out that approximately 9–12% of the cost of manufacturing a car is spent on energy, and for every 20% reduction in energy consumption, the final manufacturing cost will drop by roughly 2–2.4%. Therefore, reducing energy consumption plays a vital role in protecting the environment and boosting business competitiveness.

The assembly line balancing problem (ALBP) was first raised by Bryton [3], and refers to assigning tasks to workstations to achieve the optimization objective. The ALBP can be divided into four types according to different inputs and objectives, i.e., minimizing the number of workstations with a given cycle time is called type-1 ALBP. Minimizing the cycle time given the number of workstations is called type-2 ALBP. If the number of workstations and cycle time are unknown simultaneously, maximizing the line efficiency is labeled type-E ALBP. Aiming to find a feasible balancing solution when both are given is type-F ALBP.

The ALBP with robots is called the robotic assembly line balancing problem (RALBP), which was first proposed by Rubinovitz and Bukchin [4], and is a significant problem in the industrial sector. Since different types of robots have different processing task times and energy consumption per unit of time, the allocation of robots also needs to be considered in RALBP. In this paper, we consider minimizing the number of workstations with a given cycle time, i.e., type-1 RALBP, to be the primary objective and minimizing energy consumption based on the optimal number of workstations to be the secondary objective. Further, we introduce the “cross-station task” design, which is quite popular in practice but is rarely considered in academic settings [5], to improve production efficiency in the RALBP, and propose a novel mixed integer linear mathematical model for this problem. A simulated annealing algorithm encapsulating a restart mechanism and an improvement rule are developed to solve the problem.

The type-1 ALBP has been widely studied in the literature. Kilincci [6] presented a heuristic algorithm based on the Petri net approach to solve the type-1 simple ALBP. Manavizadeh et al. [7] solved a U-shaped balancing type-1 problem with different types of workers and designed an alert system based on the optimal number of stations to balance workload. A simulated annealing algorithm (SA) was used to solve this problem. Li et al. [8] investigated 14 meta-heuristics for type-1 two-sided ALBP and two new decoding schemes with a reduced search space developed. Comprehensive experiments have shown that the improved iterated greedy algorithm is the most efficient in solving the benchmark problems. Li et al. [9] investigated type-1 assembly line balancing considering uncertain task time. An algorithm based on the branch and bound remember algorithm was developed to solve this problem, and the effectiveness of the algorithm was demonstrated. Li et al. [10] incorporated uncertain task time attributes in type-1 U-shaped ALBP. They proposed an algorithm based on the branch and bound remember algorithm to solve this problem. Zhang [11] proposed an immune genetic algorithm (IGA) which aimed to minimize the number of workstations as well as the workload. Baskar and Anthony Xavior [12] investigated a few heuristic algorithms based on slope indices, which is a method of assigning tasks to stations, to solve the type-1 simple ALBP. Pınarbaṣı and Alakaṣ [13] formulated a constraint programming (CP) model for type-1 ALBP considering assignment restrictions. The author compared the results of different models and showed that CP is the best one. Huang et al. [14] considered a mixed-model two-sided ALBP that aimed at minimizing the number of mated-stations. A combinatorial Benders-decomposition-based exact algorithm was used to solve the proposed problem. The computational tests showed that this algorithm can obtain exact results on large-sized problem instances.

Ever since Rubinovitz and Bukchin [4] came up with RALBP and proposed an efficient heuristic to solve it [15], it has become a prevalent research direction for ALBP. Hong and Cho [16] solved the type-1 RALBP considering assembly cost. A simulated annealing algorithm was utilized as the optimization tool. Gao et al. [17] proposed an innovative genetic algorithm (GA) hybridized with local search to solve the type-2 RALBP. Five local search procedures were developed to enhance the search ability of GA. Li et al. [1] designed a cuckoo search method through different neighborhood generation methods to solve the two-sided RALBP. The computational tests showed that the proposed algorithm outperformed other meta-heuristics. Janardhanan et al. [18] considered sequence-dependent setup times for RALBP to minimize the cycle time. They proposed a migrating birds optimization algorithm (MBO) and demonstrated the effectiveness of the MBO. Sun and Wang [19] developed a hybrid algorithm that combines the branch-and-bound (B&B) and estimation of the distribution algorithm to minimize the cycle time on the robotic assembly line. Aslan [20] investigated an two-sided RALBP with sequence-dependent setup times, and a variable neighborhood search (VNS) algorithm was utilized to solve this problem.

Other features of RALBP have also been studied. Michels et al. [21] studied spot welding robotic assembly lines based on an automotive company located in Brazil. A mixed-integer linear programming (MILP) model was developed. Pereira et al. [22] solved cost-oriented RALBP (cRALBP), taking into account that different types of robots have different costs. Rabbani et al. [23] investigated four-sided human–robot collaborations on ALBP, where the tasks are performed on the left, right, above, and beneath sides. An augmented multi-objective particle swarm optimization was used to solve the model. Koltai et al. [24] analyzed the short- and long-term effects of adding robots to human ALs for the operation of the line. The use of the models was demonstrated using a case study involving a power inverter. Lahrichi et al. [25] investigated two variants of type-2 RALBP with sequence dependence. The first variant is given different types of robots, each of which can be arbitrarily assigned to multiple stations. Another variant is that given a group of robots, each robot can only be assigned to one station.

Further, the use of robots on assembly line creates energy consumption problems; some scholars treat energy consumption as one of the optimization objectives. Mukund Nilakantan et al. [26] proposed models with dual objectives to minimize the cycle time and total energy consumption simultaneously. The particle swarm optimization was used to solve this problem. Nilakantan et al. [27] proposed a multi-objective co-evolutionary algorithm to solve the energy-related RALBP. Zhang et al. [28] investigated a U-shaped RALBP and developed a multiobjective mixed-integer non-linear model to optimize carbon emissions. Hybrid Pareto–grey wolf optimization (HPGWO) was designed, and its effectiveness was demonstrated. Zhou and Wu [29] aimed to optimize the total energy consumption and a productivity-related objective simultaneously in RALBP. A novel algorithm based on a well-known enhanced decomposition-based multi-objective algorithm (MOEA/D) was designed to solve this problem. Zhang et al. [30] investigated mixed-model U-shaped RALBP and proposed a hybrid multi-objective dragonfly algorithm (HMODA) to achieve the goals of energy saving and efficiency. Belkharroubi and Yahyaoui [31] minimized energy consumption on a mixed-model RALBP. A cuckoo search algorithm, which was based on the memory principle, was developed to tackle this problem. The authors tested its effectiveness by comparing other algorithms.

By analyzing the previous research works, we can conclude that the RALBP had been studied extensively from various angles. However, the mathematical models are always nonlinear, which is not desired for a commercial solver specialized in solving mixed-integer problems, e.g., CPLEX. We did not find any literature about the type-1 RALBP with the energy consumption objective. Further, the multi-functional robots and their implied application to the assembly line regarding the cross-station design are absent.

The contribution of our paper is as follows: (1) To our best knowledge, we did not find the studies of the multi-objective optimized type-1 RALBP considering energy consumption. Thus, this work fills the research gap in RALBP. (2) We introduce the “cross-station task” design, which has already been applied in practice but rarely studied academically, into type-1 RALBP for the first time. (3) We leverage and modify the simulated annealing algorithm for solving this problem, where incorporates an improvement mechanism of exact algorithms.

The remainder of this paper is organized as follows. Section 2 describes the cross-station task design in detail, and a simple example is presented. We propose a MILP model considering the cross-station task design in Section 3. A simulated annealing algorithm is designed for the problem in Section 4. Computational results are shown in Section 5. Section 6 concludes the paper.

2. RALBP-CS Design

In this section, we introduce the cross-station task design to reduce the idle time of each station as much as possible on the assembly line. This idea is similar to certain other studies. Grzechca and Foulds [32] relaxed the assumption that a task cannot be split among two or more stations, i.e., a task can be split into multiple subtasks, then changed the priority graph for research. Nanda and Scher [33] relaxed the assumption and studied overlapping workstations, where a task can be processed by a pair of workstations simultaneously.

In the cross-station task design, a task could be processed at three stations, which is a more realistic design than the previous two designs in some manufacturing systems. The cross-station task design is a practical application [5]. The three stations include the current station and its front and rear stations, if they exist. To achieve this, one station can “borrow” (“lend”) its cycle time from (to) its front or rear stations. If this task is assigned to the very front part of the current station, it could be processed in advance at the front station. That is, the current station borrows its cycle time from the front station. If this task is assigned to the very rear part of the current station, it could be processed with a delay at the rear station. That is, the current station borrows its cycle time from the rear station. For example, in Figure 1, task 2 is originally assigned to station 2. Since station 2 has borrowed a portion of the cycle time of station 1, task 2 can start being processed in advance at station 1. Likewise, task 4 is originally assigned to station 3. Since station 2 has lent a portion of its cycle time to station 3, task 4 can start being processed in advance at station 2. There are two points worth noting: (1) Tasks can only be assigned to one station and one robot, but they can be processed when the work-in-process (WIP) is at adjacent stations. (2) A robot is multi-functional with different robotic arms, as mentioned in Section 1. For example, robot 3 is processing task 4 with one robotic arm and operating task 6 with another arm.

Then, a simple example is presented.

Example 1. 

To intuitively recognize the advantages of this design, suppose there is only one task sequence and a type of robot, which is shown in Figure 2. The task number is stored in the node, and the number outside the code displays the time the robot takes to process the task. There is a given cycle time of 11.

Task assignment is shown in Figure 3. The shaded part represents idle time. Without the RALBP-CS design, tasks 1, 2, and 3 are assigned to station 1; tasks 4, 5 and 6 are assigned to station 2; and tasks 7, and 8 are assigned to station 3. Thus, there are 3 stations installed, and some idle time is incurred on the line. If the RALBP-CS design is applied to the line, tasks 1, 2, 3, and 4 are assigned to station 1, which borrows 1 unit of the cycle time of station 2. Then, tasks 5, 6, 7, and 8 are assigned to station 2. The number of stations that are installed is two (one less than the line without considering RALBP-CS design), and there is no idle time at all on line.

3. Mathematical Modeling

In this section, the MILP mathematical model is formulated. The primary goal is to minimize the number of workstations. The secondary objective is to minimize total energy consumption. The decision variables are summarized at

Table 1. Notations.

Parameters	Descriptions
n	Total number of tasks
R	Total number of robot types
J	The maximum number of workstations that are allowed to be opened
m	The number of workstations that are actually installed
$i,h$	Index of tasks, $i,h=1,2,\cdots n$
$s,j$	Index of stations. $s,j=1,2,\cdots J$
r	Index of robots. $r=1,2,\cdots R$
c	Cycle time
$\omega$	Weight coefficient
$Rt{e}_s$	The remaining capacity at station s
$TEC$	Total energy consumption
$TE{C}_{max}$	The upper bound of total energy consumption
$OE{C}_r$	Operation energy consumption of the robot r per time unit
$SE{C}_r$	Standby energy consumption of the robot r per time unit
$t_{ir}$	The task $i^{\prime }s$ processing time by robot r
$Pr\left(i\right)$	Set of direct predecessors of task i
$\gamma$	Maximum amount of time that can be borrowed from one station by another
$\varphi$	A large positive number
Decision variables	Descriptions
$x_{ij}$	1, if task i is assigned to workstation j; 0, otherwise
$y_{rj}$	1, if robot r is allocated to workstation j; 0, otherwise
$z_{irj}$	1, if task i and robot r are assigned to workstation j; 0, otherwise
$d_{j,s}$	1, if station j borrows time from station s; 0, otherwise
$q_{j,s}$	A positive value shows the amount of time station j borrows from station s; 0, otherwise

.

3.1. Assumptions

The basic assumptions underlying the problem are as follows.

• One single product is manufactured on the assembly line.
• Robots are multi-functional with numerous arms that can handle different tasks simultaneously.
• The precedence relations between the tasks are given previously.
• A task can only be assigned to one station and one robot.
• Each station can only borrow time from its adjacent stations.
• The task-processing time is dependent on the type of robot assigned to it.
• Each robot can be assigned to any station and can process any task.

The notations are presented in Table 1 and used throughout the paper.

3.2. Formulation

In the model, $TEC$ represents the total energy consumption. $TE{C}_{max}$ represents the upper bound of total energy consumption, which is a fixed parameter by taking the maximum operating and idle energy consumption of the robots for each task, and then summing them. Thus, $TEC/TE{C}_{max}$ is in the range [0, 1]. Now, the mathematical model is presented.

$$\begin{array}{cc}\hfill min& Obj=m+TEC/TE{C}_{max},\hfill \end{array}$$

(1)

$$\begin{array}{cc}\hfill s.t.& m=\sum _{r=1}^R\sum _{j=1}^J{y}_{rj},\hfill \end{array}$$

(2)

$$\begin{array}{cc}\hfill & TEC=OEC+SEC,\hfill \end{array}$$

(3)

$$\begin{array}{cc}\hfill & OEC=\sum _{j=1}^J\sum _{r=1}^R\sum _{i=1}^{n}OP{C}_r{z}_{irj}{t}_{ir},\hfill \end{array}$$

(4)

$$\begin{array}{cc}\hfill & SEC=\sum _{j=1}^J\sum _{r=1}^R{g}_{rj}SP{C}_r,\hfill \end{array}$$

(5)

$$\begin{array}{cc}\hfill & g_{rj}\le c+q_{j,j+1}+q_{j,j-1}-q_{j+1,j}-q_{j-1,j}-\sum _{r=1}^R\sum _{i=1}^n{z}_{irj}{t}_{ir}+(1-y_{rj})\psi ,\forall j=1,\cdots ,J,\hfill \end{array}$$

(6)

$$\begin{array}{cc}\hfill & g_{rj}\ge c+q_{j,j+1}+q_{j,j-1}-q_{j+1,j}-q_{j-1,j}-\sum _{r=1}^R\sum _{i=1}^n{z}_{irj}{t}_{ir}-(1-y_{rj})\psi ,\forall j=1,\cdots ,J,\hfill \end{array}$$

(7)

$$\begin{array}{cc}\hfill & \underset{r=1}{\sum ^R}{y}_{rj}\le 1,\forall j=1,\cdots ,J,\hfill \end{array}$$

(8)

$$\begin{array}{cc}\hfill & \sum _{r=1}^R{y}_{rj}\ge x_{ij},\forall j=1,\cdots ,J,\forall i=1,\cdots ,n,\hfill \end{array}$$

(9)

$$\begin{array}{cc}\hfill & \sum _{r=1}^R{y}_{rj}\le \sum _{i=1}^n{x}_{ij},\forall j=1,\cdots ,J,\hfill \end{array}$$

(10)

$$\begin{array}{cc}\hfill & \sum _{r=1}^R{y}_{rj}\ge \sum _{r=1}^R{y}_{rj+1},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(11)

$$\begin{array}{cc}\hfill & \sum _{j=1}^J{x}_{ij}=1,\forall i=1,\cdots ,n,\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill & \underset{i=1}{\sum ^n}j{x}_{hj}\le \underset{i=1}{\sum ^n}j{x}_{ij},\forall h\in p\left(i\right),\hfill \end{array}$$

(13)

$$\begin{array}{cc}\hfill & x_{ij}+y_{rj}\le z_{irj}+1,\forall i=1,\cdots ,n,\forall r=1,\cdots ,R,\forall j=1,\cdots ,J,\hfill \end{array}$$

(14)

$$\begin{array}{cc}\hfill & \left(1-x_{ij}\right)+y_{rj}\le \left(1-z_{irj}\right)+1,\forall i=1,\cdots ,n,\forall r=1,\cdots ,R,\forall j=1,\cdots ,J,\hfill \end{array}$$

(15)

$$\begin{array}{cc}\hfill & x_{ij}+\left(1-y_{rj}\right)\le \left(1-z_{irj}\right)+1,\forall i=1,\cdots ,n,\forall r=1,\cdots ,R,\forall j=1,\cdots ,J,\hfill \end{array}$$

(16)

$$\begin{array}{cc}\hfill & \left(1-x_{ij}\right)+\left(1-y_{rj}\right)\le \left(1-z_{irj}\right)+1,\forall i=1,\cdots ,n,\forall r=1,\cdots ,R,\forall j=1,\cdots ,J,\hfill \end{array}$$

(17)

$$\begin{array}{cc}\hfill & q_{j,s}\le \gamma ,\forall j=1,\cdots ,J,\forall s=1,\cdots ,J,\hfill \end{array}$$

(18)

$$\begin{array}{cc}\hfill & d_{j,j+1}+d_{j+1,j}\le 1,\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(19)

$$\begin{array}{cc}\hfill & \phi d_{j,j+1}\ge q_{j,j+1},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(20)

$$\begin{array}{cc}\hfill & \phi d_{j+1,j}\ge q_{j+1,j},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(21)

$$\begin{array}{cc}\hfill & q_{j+1,j}\ge 0.1d_{j+1,j},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(22)

$$\begin{array}{cc}\hfill & q_{j,j+1}\ge 0.1d_{j,j+1},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(23)

$$\begin{array}{cc}\hfill & \sum _{r=1}^R{y}_{rj+1}\ge d_{j,j+1},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(24)

$$\begin{array}{cc}\hfill & \sum _{r=1}^R{y}_{rj+1}\ge d_{j+1,j},\forall j=1,\cdots ,J-1,\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill & q_{1,0},q_{0,1},q_{J,J+1},q_{J+1,J}=0,\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill & q_{j,s}\ge 0,\forall j=1,\cdots ,J,\forall s=1,\cdots ,J,\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill & g_{rj}\ge 0,\forall r=1,\cdots ,R,\forall j=1,\cdots ,J,\hfill \end{array}$$

(28)

Equation (1) shows the objective function, which represented by the primary (m) and secondary objective ($TEC$). Constraint (2) calculates the number of workstations that are actually installed. Constraint (3) calculates the total energy consumption by summing the total operation energy consumption (Constraint (4)) and standby energy consumption (Constraint (5)) on the assembly line. Constraints (6) and (7) calculate the idle time for each station, and if the robot r is allocated to the station j ($y_{rj}=1$), the constraints are active. Constraint (8) refers to the requirement that, at most, one robot can be allocated to the station. Constraint (9) ensures that tasks are assigned only to stations that are installed. Constraint (10) ensures that the installed station is not empty. Constraint (11) ensures the stations are installed continuously in turn. Constraint (12) ensures a task can only be assigned to one station. Constraint (13) refers to the priority constraint. Constraints (14)–(17) demonstrate the logical relationship between tasks, robots, and workstations. Constraint (18) limits the upper bound of time borrowing from one station to another. Constraints (19)–(23) ensure that two stations cannot borrow each other’s time simultaneously. Constraints (24) and (25) ensure that the action of lending and borrowing cannot occur for the empty station. Constraints (26)–(28) are the domain constraints.

4. A Simulated Annealing Algorithm

In this section, a simulated annealing algorithm (SA) is designed to tackle the proposed problem. SA was first proposed by Kirkpatrick et al. [34], which is an optimization algorithm that imitates the gradual cooling of metals. It is a meta-heuristic including a random optimization approach, which is to avoid a local optimum by evaluating inferior solutions. It has the advantages of simple description, flexible use, wide application, high operation efficiency, and less affected by the input parameter. Starting from a randomly chosen initial solution S, SA seeks a candidate solution $S^{\prime }$ in the area surrounding the initial solution. S and $S^{\prime }$ correspond to fitness values $Obj$ and $Ob{j}^{\prime }$, respectively. Then, determine which candidate solution can be approved by comparing the fitness values of the candidate with the present solutions. The amount of change in the fitness value is referred to as $\Delta$ ($\Delta =Obj-Ob{j}^{\prime }$). If $\Delta >0$, $S^{\prime }$ is accepted; otherwise, $S^{\prime }$ is accepted with a given probability ($p=e^{-\frac{\Delta }{T}}$), where T is the temperature parameter. At the beginning, there is a high probability of accepting the inferior solution due to the higher T. In each iteration, T is decreased by a cooling schedule until a predetermined stopping requirement is satisfied.

4.1. The General Framework of SA

In this study, the optimal objective is solved by designing the iterative mechanism and developing an improvement rule based on the traditional SA. $Obj$ represents the fitness value. The notation of SA is given below.

T	Temperature parameter
$\alpha$	Cooling rate
$ite$	The iteration index
$it{e}_{max}$	The maximum number of iterations of temperature
$d{n}_{max}$	The maximum number of iterations per restart
$S{q}_{task}$	A feasible assignment sequences of task
$S{q}_{robot}$	A feasible assignment sequences of robot
$rn$, $pr$	Uniform random numbers between [0, 1]

Specifically, SA searches for the $S{q}_{task}$ and $S{q}_{robot}$ that result in the best fitness. Variable neighborhood search (VNS) is another characteristic of the SA. In SA, VNS chooses between two neighborhoods and systematically searches them. A random number ($pr$) determines whether to alter the robot sequence or the task sequence for each iteration. The iterative steps of SA are listed below.

Step 1:Input $P\left(i\right)$, T, $Nn$, $\alpha$, $OP{C}_r$, $SP{C}_r$, $t_{ir}$, J, c, $d{n}_{max}$, $TE{C}_{max}$, set $ite=1$, $dn=0$.

Step 2: Initialize sequences $S{q}_{task}$ and $S{q}_{robot}$.

Step 3: Generate the initial objective value $Obj$. Set the first three optimal objective values equal to $Obj$.

Step 4: Generate $pr$, if $pr\le 0.5$, launch the neighborhood generation mechanism of the task sequence to obtain a new $S{q}_{task}^{\prime }$; otherwise, launch the neighborhood generation mechanism of the robot sequence, and obtain a new $S{q}_{robot}^{\prime }$.

Step 5: Launch decoding process to obtain a new objective value $Ob{j}^{\prime }$.

Step 6: Calculate $\Delta =Ob{j}^{\prime }-Obj$. If $\Delta <0$, update and retain the first three optimal solutions, update $dn=0$, go to step 8; otherwise, update $dn=dn+1$, and go to step 7.

Step 7: Generate $rn$, if $rn<e^{-\frac{\Delta }{T}}$, go to step 8; otherwise, go to step 9.

Step 8: Accept and update $S{q}_{task}=S{q}_{task}^{\prime }$, $S{q}_{robot}=S{q}_{robot}^{\prime }$, $Obj=Ob{j}^{\prime }$.

Step 9: If $dn==d{n}_{max}$, activate the restart mechanism, update $dn=0$, go to step 2; otherwise, update $T=\alpha T$, $ite=ite+1$, and go to step 10.

Step 10: If $ite==it{e}_{max}$, launch the improvement mechanism, output optimal solution, done.

4.2. Initial Sequence Encoding

In the initial sequence encoding process, we employ $S{q}_{task}$ and $S{q}_{robot}$ to express the feasible assignment sequences of task and robot, respectively. In contrast to the task sequence, a feasible robot sequence can be generated randomly because the robot sequence is not constrained by precedence. The encoding details are provided below for generating $S{q}_{task}$ and $S{q}_{robot}$.

Step 1: Generate $S{q}_{robot}$, which is an array containing J random integers taken from 1 to R.

Step 2: Set $S{q}_{task}=\left[\right]$.

Step 3: Generate $S{q}_{task}^{\prime }$, which is an array containing random permutation of the integers from 1 to n.

Step 4: Based on the $S{q}_{task}^{\prime }$ and the precedence constraints, assign the task i to $S{q}_{task}=\left[\right]$, then delete the task i in $S{q}_{task}^{\prime }$.

Step 5: If task i cannot be assigned because of violating precedence relationship, skip it and then consider the next task i according to $S{q}_{task}^{\prime }$, then go to step 4.

Step 6: Repeat steps 4–5 until $S{q}_{task}^{\prime }=\left[\right]$, obtain $S{q}_{task}$, done.

4.3. Decoding of Objective Function

In the decoding process, each robot is allocated to a station in turn according to $S{q}_{robot}$. The robot allocation at stations s and $s+1$, respectively, are denoted by r and $r^{\prime }$. The initialization process (step 1) refers to loading the input data. The task assignment process is described in steps 2 to 5, where step 2 refers to assigning the task to the current station, and steps 3–5 refer to assigning the task to the current station or next adjacent station considering the cross-station design. These three points should be noted: (1) if the final task needs to borrow time of the assignment process, it is assigned to the next adjacent station directly to prevent the situation that an empty stations lend its time; (2) the current station’s available time is not $Re{t}_s$ but $Re{t}_s+\gamma$ since the station is permitted to lend or borrow time; and (3) if the task is assigned to station $s+1$, the idle time $max(Re{t}_s-\gamma ,0)$ may incur at station s, i.e., $min(Re{t}_s,\gamma )$ is the amount of time that station s lends to station $s+1$. Step 6 computes the energy consumption for station s. Eventually, the feasible solutions $Obj$ can be obtained in step 7.

Step 1: Input $t_{ir}$, J, $S{q}_{task}$, $S{q}_{robot}$, $OP{C}_r$, $SP{C}_r$, set $s=1$, $id=1$, and $Re{t}_s=c$.

Step 2: If all tasks are assigned, go to step 7; otherwise, assign the $i{d}_{th}$ task in $S{q}_{task}$ to station s, update $Re{t}_s$ ($Re{t}_s=Re{t}_s-t_{ir}$) and $id=id+1$, and go to step 3.

Step 3: If $t_{ir}>Re{t}_s$ and $id==n$, assign the task $i=S{q}_{task}\left(id\right)$ to station $s+1$, set $q_{s,s+1}=0$ and $q_{s+1,s}=0$, update $s=s+1$, and compute $OE{C}_s$ and $SE{C}_s$, go to step 7; elseif $t_{ir}>Re{t}_s$ and $id<n$, go to step 4; otherwise, go to step 3.

Step 4: If $t_{ir}\le \gamma +Re{t}_s$ and $t_{i{r}^{\prime }}+max(Re{t}_s-\gamma ,0)\ge t_{ir}$, assign the task $i=S{q}_{task}\left(id\right)$ to station s, and set $q_{s,s+1}=t_{ir}-Re{t}_s$, $q_{s+1,s}=0$, update $Re{t}_{s+1}$, where $Re{t}_{s+1}=c-q_{s,s+1}$, go to step 6; otherwise, go to step 5.

Step 5: Assign the task $i=S{q}_{task}\left(id\right)$ to station $s+1$, set $q_{s,s+1}=0$ and $q_{s+1,s}=min(Re{t}_s,\gamma )$, update $Re{t}_{s+1}$, where $Re{t}_{s+1}=c+q_{s+1,s}-t_{ir}$, and go to step 6.

Step 6: Compute $OE{C}_s$ and $SE{C}_s$, update $id=id+1$, and $s=s+1$, go to step 2.

Step 7: Get m, where $m=s$, compute $TCF$, and output $Obj$.

The decoding operation of objective function is then illustrated with an example.

Example 2. 

Consider the precedence relationship graph given in Figure 4 and the parameters are provided in

Table 2. Parameters for example 2.

Variables and Parameters	Value
n	8
R	3
J	5
c	11
$\gamma$	2
$TE{C}_{max}$	11.48
$OE{C}_r$	[0.3; 0.25; 0.32]
$SE{C}_r$	[0.03; 0.025; 0.032]

. $S{q}_{task}=\{1,2,4,3,5,6,7,8\}$, $S{q}_{robot}=\{3,2,2,1,3\}$. Tasks 1 and 2 are assigned to station 1 and update $Re{t}_1$, $Re{t}_1=3$. Then we should assign task 4 according to $S{q}_{task}$ since $t_{4,3}>Re{t}_1$ and task 4 is not the last. We should take into account the cross-task design. By executing step 4, $4<3+2$ and $3+max(3-2,0)=4$, task 4 should be assigned to station 1 and station 1 shall borrow 1 unit of time from station 2. Update $Re{t}_2$, $Re{t}_2=10$, tasks 3 and 5 are assigned to station 2, and update $Re{t}_2$, $Re{t}_2=1$. Task 6 is assigned to station 3 due to $4>1+2$, and station 2 lends 1 unit of time to station 3. Task 7 is assigned to station 3 and we update $Re{t}_3$, $Re{t}_3=3$. When assigning task 8, we find $t_{8,2}>Re{t}_3$ and task 8 is the last, and thus task 8 is assigned to station 4 directly. Finally, a feasible solution can be found, where $m=4$, $TCF=9.825$, and $Obj=4.856$.

4.4. Neighborhood Generation and Restart Mechanism

In SA, an insert method mentioned by Khorasanian et al. [35] is used for generating a neighbor of the task sequence. Simply put, a new task sequence $S{q}_{task}$ can be generated by relocating a task to a different position. The reader can refer to the cited literature for more details on the neighborhood generation of task sequences. For neighborhood generation of robot sequences, we randomly select stations with the robot that have been installed, and then randomly select a different type of robot to replace to obtain a new robot sequence $S{q}_{robot}$.

In SA, as we know, local optimality can be escaped by accepting inferior solutions. As the temperature decreases, the probability of accepting the inferior solution becomes smaller, and the easier it is to fall into the local optimality. To address this issue, we designed a restart mechanism with reference to Li et al. [36]. If the optima are not improved in $d{n}_{max}$ consecutive iterations, the algorithm returns to the initial solution generation phase.

4.5. Improvement Mechanism

In this section, we propose a novel improvement rule, which embeds the exact algorithm into the SA algorithm to improve the quality of the solution.

As we know, the MILP model can be solved using exact algorithms or heuristic algorithms. Exact algorithms can find the optimal solution to the model, but for the complex assembly line problem, it is difficult to obtain a feasible solution when the allowable time is limited. Therefore, researchers generally use heuristic algorithms to obtain an approximate optimal solution. However, heuristic algorithms tend to fall into the local optimality, and the gap between the approximate optimal solution and the actual optimal solution cannot be measured.

In the improvement mechanism, we cut the original problem into a few small problems to find a better solution using exact algorithms. That is, most of the variables in RALBP are fixed, and only the remaining variables are relaxed. Based on the SA results, we select relaxed tasks and robots based on the three rules given in

Table 3. Improvement rules.

	Rules Description
Rule 1	The robots and tasks assigned to the last station are relaxed
Rule 2	Compare the first 3 approximate optimal solutions of SA, the task and robot of assigning different positions are relaxed
Rule 3	10% of the tasks and robots are randomly relaxed in the remaining sequence (upper limit rounding)

. In Example 3, the effectiveness of the improvement mechanism is shown.

Example 3. 

To test the effectiveness of the improvement mechanism, we compare the results before and after the introduction of the improvement mechanism. The sub-problems are derived from the datasets described in Section 5.1. The results of the comparison are shown in Figure 5. In Figure 5, the same color represents the same cycle time in datasets (Arcus, Heskiaoff, Scholl). Obviously, after the introduction of the improvement mechanism, although m has not changed, $TEC$ has become smaller for datasets of different sizes. Thus, the improvement mechanism we propose is effective.

5. Computational Experiments

5.1. Design of Experiment

The basic datasets are extracted from a well-known database (https://assembly-line-balancing.de/, accessed on 30 August 2022). They are Heskiaoff (28), Kilbrid (45), Arcus (83), and Scholl (297). The numbers inside the parentheses indicate the total number of tasks of that dataset. The task time $t_{ir}$ is randomly generated based on the original data according to the fact that the higher the energy consumption, the lower the efficiency. $SP{C}_r$ and $OP{C}_r$ are selected by referring to Nilakantan et al. [27]. For each instance, c is fixed at six different values, and $\gamma$ is set to the $0.1\times c$. Hence, there is a total of 24 independent experiments to conduct.

The particle swarm algorithm (PSO) and the late acceptance hill-climbing algorithm (LAHC) are two traditional methods that are compared. To observe the quality of each algorithm, we used the Gurobi 9.1.2 optimizer to solve the MILP model. Due to the excessive time of the exact algorithm for solving large instances, the runtime limit is set to 3600 s and the gap value is returned. To ensure that the heuristic algorithms are comparable, constrain the algorithm runtime ($rt$) to $rt=10\times n$ seconds. These algorithms are implemented in Matlab (R2019a) and executed on an AMD Ryzen 55500U 2.10 GHz CPU.

We have seen from the preliminary experiment results that the optima are not parameter sensitive. As a result, the parameter values are taken from the literature, as in

Table 4. Parameter values for each algorithm.

Parameters	SA	LAHC	PSO
Cooling rate	0.9	-	-
Length of cost list	-	100	-
Learning coefficient $l_1\left(l_2\right)$	-	-	2(2)
The number of task(robot) particles	-	-	30(30)

. It should be noted that the initial temperature is case-dependent. The initial temperature in SA is determined using the methods described in Li et al. [36].

5.2. Results and Analysis

The computational results are displayed in

Table 5. Computational results.

Dataset	c	Gurobi		SA	PSO	LACH
		Obj	Gap (%)	Obj	Obj	Obj
Heskiaoff	160	7.7150	0.0	7.7153	7.7236	7.7235
	190	6.6989	0.0	6.7057	6.7041	6.7085
	220	5.6799	0.0	5.6848	5.6857	5.6832
	250	4.7058	0.0	5.6789	5.6782	5.6860
	280	4.6507	0.0	4.6518	4.6559	4.6548
	310	4.6435	0.0	4.6449	4.6538	4.6590
Kilbrid	70	8.7203	0.0	8.7528	8.7739	9.7163
	90	7.6807	0.0	7.6842	7.6889	7.6863
	110	5.6852	0.0	5.7273	5.7293	6.6619
	130	5.6313	0.0	5.6328	5.6334	5.6364
	150	4.6068	0.0	4.6105	4.6123	4.6190
	170	4.5893	0.0	4.5904	4.5906	4.5935
Arcus	4200	25.7511	52.6	18.7532	19.7510	19.7233
	4500	–	–	17.7538	17.7517	18.7151
	4800	17.7018	58.6	16.7229	16.7377	17.7113
	5100	–	–	15.7267	15.7277	16.7014
	5400	–	–	14.7218	14.7395	15.6946
	5700	14.6807	35.4	14.6866	14.7082	14.6911
Scholl	2000	–	–	36.7751	36.8018	37.7644
	2300	–	–	31.7916	31.7875	32.7511
	2600	–	–	28.7415	28.7516	28.7494
	2900	–	–	25.7373	25.7472	26.7213
	3200	–	–	22.7629	22.7809	23.7187
	3500	–	–	21.7004	21.7137	21.7110

. The best results each algorithm can obtain are recorded in column $Obj$. $Obj$ is calculated by Formula (1), which contains information in both m and $TEC$. Due to $TEC/TE{C}_{max}$ is in the range [0, 1], before and after the decimal point are our primary objective (m) and secondly objective ($TEC$), respectively. When the runtime is reached but the Gurobi optimizer cannot return a result, it is denoted by –. The unique optimal result between the three heuristics is marked in bold.

Compared with three heuristic algorithms, the Gurobi optimizer returns the optimal solution for each instance (gap = 0) of the first two datasets. Thus, we can conclude that exact algorithms can quickly get a feasible solution and is optimal for instances with a small number of tasks. Additionally, 9 out of the 12 primary objective m of the first two datasets are the same with three heuristic algorithms, indicating that the heuristic can find solutions as well as the exact algorithm for small instances.

However, when solving a problem with a large number of tasks, exact algorithms may find a solution with a large gap (Arcus) or not even find any feasible solution (Scholl), and the quality of the feasible solution may also be worse than that of the heuristic algorithms. Therefore, for large ALBP problems, heuristics are better than the exact algorithm.

Comparing the results among the three heuristic algorithms, the SA algorithm finds the best optimal solution where 18 out of 24 are the unique best, dominated by PSO in 5 instances, and is dominated by LACH in 1 instance. For the SA algorithm, the number of stations m is optimal among the three heuristics. In addition, in the first dataset, the SA algorithm finds the best optimal solutions where 3 out of 6 are the unique best. The SA algorithm finds the best optimal solutions where 5 out of 6 are the unique best in the remaining three datasets. Thus, the SA algorithm is much better for solving large instances.

6. Conclusions

A satisfactory ecological environment is an important part of people’s pursuit of a better life. Pollution from energy consumption in the industrial sector is a problem that cannot be ignored. Presently, robotic assembly lines are widely applied in industrial production. Though the introduction of multi-functional robots on assembly line results in a significant improvement in production efficiency, it brings about high energy consumption. Thus, how to balance energy consumption and efficiency is the goal of our paper.

In this paper, a robotic assembly line balancing problem considering minimizing the number of workstations as the primary objective and energy consumption as the secondary objective is investigated. Our research is the first attempt to model and solve the type-1 RALBP with multi-objectives and cross-station task design. A mixed integer linear integer programming model is formulated to solve the problem. A simulated annealing algorithm which encapsulates an improvement mechanism, is designed and compared with the particle swarm algorithm and the late acceptance hill climbing algorithm. The computational study shows that SA performs better than PSO and LAHC.

This study has some limitations. Since it is the first attempt to explore this innovative research topic, a simple single product is assumed, which is less useful than a general multi-product assumption. Additionally, we only represented three classic algorithms (SA, PSO, and LAHC) to solve the straight assembly line. Algorithmic design and varieties can be further improved to solve more complex assembly line balancing problems (two-sided, U-shaped, and parallel).