Balancing of assembly lines with collaborative robots

The role of automation in modern manufacturing companies has increased significantly over the past decades. Several types of automated equipment, such as industrial robots, are frequently included in production systems (Graves and Redfield 1988). In 2017, for instance, worldwide robot sales reached 374,000 units, an increase of 217% compared to 2010. This growth is mainly driven by the automotive and electronics industry (International Federation of Robotics 2018), where industrial robots are utilized in assembly lines to ensure the companies’ ability of high-volume production at low costs. Additionally, the use of highly automated assembly lines assures standardized product quality and process safety (Boysen et al. 2008). As a result of the evolving role of automation technology, enterprises predominantly focused on achieving economy of scale by standardization of processes and inclusion of industrial robots (Hu et al. 2011).

In the current state, however, manufacturers cannot efficiently automate many tasks as the established robot technology does not provide the required degree of flexibility. Consequently, economy of scope is achieved by manual assembly utilizing human advantages in manufacturing corporations and small- and medium-sized enterprises (SMEs) (Antonelli et al. 2016; Hu et al. 2011; Krüger et al. 2009; Michalos et al. 2014). Humans comprise characteristics like flexibility, adaptability, decision making skills, and creativity while strength, endurance, speed, and accuracy are attributes of robots (Helms et al. 2002; Michalos et al. 2014). To remain competitive, manufacturing enterprises have to introduce new production concepts to increase their performance.

Human–robot collaboration (HRC) is an emerging technology in the field of novel production systems. By introducing stations with collaborative task execution by workers and robots, the advantages of both automated and manual production lines can be realized in a combined production system. As a result, the production efficiency and quality can increase. Additionally, the introduction of HRC can be beneficial for the workers’ states of health if the robot executes ergonomically stressful and repetitive tasks. This is of particular importance against the background of demographic change (Schmidtler and Bengler 2015). Further advantages arise from the possibility of parallel work from either side of the station. The length of the assembly line may decrease, which results in higher space utilization. Also, the robot as an additional resource reduces the production lead time. In addition, material handling, workers’ movement, and set-up times may also be reduced (Bartholdi 1993; Lee et al. 2001).

Manufacturers name manifold application areas for collaborative robots (Kuka 2018; Universal Robots A/S 2018b) and they have been successfully implemented in both manufacturing corporations (BMW Group 2013; Daimler 2014; Volkswagen 2018) and SMEs (Fraunhofer IAO 2016; International Federation of Robotics 2015a, b, c). Despite its increasing distribution in real-world industry applications, the trend of human–robot collaboration has not yet been considered in the balancing of assembly lines, and many companies state the necessity of additional support for the planning process (Fraunhofer IAO 2016).

Aside from assigning tasks to the stations of the assembly line under the consideration of precedence relations (assembly line balancing), further challenges arise for the balancing of assembly lines with collaborative robots. Since robots are considered as additional resources, it has to be decided about the allocation of a limited number of collaborative robots to the manual stations of the assembly line (equipment selection). For stations with robots, tasks also have to be allocated to the resources (worker and/or robot) overtime. Consequently, the assembly line balancing problem with equipment selection is enriched by a collection of scheduling problems. In scheduling these stations, logical relations between the resources have to be considered. For instance, a task can only be performed collaboratively if neither the worker nor the robot is occupied by a different task (scheduling with logical relations). Additionally, these modes have different efficiency. Collaborative execution by a worker and a robot, for instance, is faster than execution only by the human worker (allocation-dependent task times), leading to a tradeoff between time and resource consumption.

From the challenges described above, a novel planning problem for assembly line balancing arises, which we strive to investigate in detail. Our contribution is fourfold. First, since there are a multitude of possible applications for collaborative robots in industrial manufacture, we discuss possible fields of application and limit the scope of our contribution toward the balancing of assembly lines with collaborative robots. Second, a mathematical optimization model of the considered assembly line balancing problem is presented. Third, we develop a hybrid genetic algorithm to solve larger problems. Fourth, by conducting an extensive computational experiment, the performance of the mathematical optimization model and the genetic algorithm is analyzed, and general recommendations for decision makers wavering with collaborative robots’ implementation are derived.

The remainder of this contribution is structured as follows: in the next section, we introduce the problem of balancing assembly lines with collaborative robots based on the classification of the problem setting and an illustrative example. Subsequently, we review the relevant literature in the field of assembly line balancing problems in Sect. 3. A mathematical formulation for the human–robot collaborative assembly line balancing and scheduling problem is introduced in Sect. 4. The hybrid genetic algorithm is presented in Sect. 5. In Sect. 6, we deliver insights into computational results. The paper closes with a conclusion and an outlook for future research in Sect. 7.

In recent years, the concept of collaboration has received increasing attention in production (e.g., Leng and Jiang 2018; Salamati-Hormozi et al. 2018), logistics (e.g., Basso et al. 2019; Guajardo et al. 2018), and supply chain management (e.g., Herczeg et al. 2018; Ponte et al. 2018). In this context, collaboration is typically seen as a form of cooperation between two or more independent companies planning and executing jointly specific operations. The aim is to achieve mutual benefits, which can be related to cost reductions or the compliance with environmental regulations, for instance. Most commonly, cooperation can either take place between (competing) companies on the same stage of a supply chain (horizontal collaboration) or among partners that operate on different supply chain levels (vertical collaboration) (Basso et al. 2019; Simatupang and Sridharan 2002).

In this paper, in contrast, we are concerned with another form of collaboration, namely the cooperation of robots and human workers on the shop floor (Krüger et al. 2009; Tsarouchi et al. 2016a, b). In particular, we consider the balancing of manual assembly lines, in which collaborative robots either support manual task execution by human workers or perform tasks themselves as an additional resource. In this field, two relevant streams of literature can be distinguished. The first stream discusses the allocation of equipment (robots) with different capabilities to stations of a production system and is referred to as equipment selection problem. The second stream is concerned with scheduling problems within the context of assembly line balancing.

In the stream of equipment selection problems, automated assembly lines are examined. The first to explicitly consider industrial robots in line balancing were Rubinovitz et al. (1993). They stress the practical relevance of task times, which are dependent on the specific robot, and consider these in their algorithm to solve the robotic assembly line balancing problem (RALBP). In the recent literature, only few papers are devoted to RALBP with the objective of minimizing the cycle time. Levitin et al. (2006) develop a genetic algorithm (GA) for the RALBP to maximize the production rate and conduct experiments on randomly generated test sets. To improve results and reduce computational effort, Gao et al. (2009) propose a GA and combine it with heuristic local search procedures. They suggest an integer non-linear programming model and compare its optimal results with results from their GA and results from the aforementioned paper. Yoosefelahi et al. (2012) propose a mixed-integer programming (MIP) model with multiple objectives. They aim at minimizing the cycle time, robot investments, and robot setup costs and solve the problem with different evolution strategies. Results of the different strategies are compared among each other. Mukund Nilakantan and Ponnambalam (2015) consider a U-shaped robotic assembly system and propose a 0–1 integer programming model and particle swarm optimization approach. Müller et al. develop an approach for the redundant configuration of automated assembly lines to mitigate the effect of robot failures (Müller et al. 2016, 2017, 2018). Pereira et al. (2018) pursue a cost-oriented approach on the robotic assembly line balancing problem. Novel solution procedures for the RALBP are proposed by Borba et al. (2018).

Overall, the contributions in this stream of literature consider allocation-dependent task times, since the equipment types are associated with different levels of efficiency when performing the tasks. These assumptions are very similar to a literature stream on the assembly line worker assignment and balancing problem (ALWABP) for manual assembly lines based on the contribution of Miralles et al. (2007). In the ALWABP, a heterogeneous workforce has to be assigned to stations, where processing times depend on the actual worker. In neither RALBP nor ALWABP, however, decisions on collaboration of resources are taken into account.

In the second stream, assembly line balancing problems with consideration of scheduling components for (certain) stations are considered. These problems arise, if multiple resources are assigned among a common station and may consequently execute tasks at the same workpiece in parallel. In this field, assembly lines with multi-manned stations are of particular importance. In this problem, tasks and workers have to be allocated among the stations and tasks are explicitly (and exclusively) assigned to the workers. The minimization of the number of workers is pursued by Roshani et al. (2013) and Kellegöz and Toklu (2015). Fattahi et al. (2011) minimize the number of workers as a primary objective and the number of stations as a secondary objective. An improved mathematical formulation for the same problem is proposed by Kellegöz (2016). The minimization of cycle time with the secondary objective to minimize the number of workers is proposed by Roshani and Giglio (2017). An extension toward multiple sides within each station is presented by Naderi et al. (2018). Common tasks to be executed by more than one worker simultaneously are suggested by Yazgan et al. (2011) and Sikora et al. (2017). The collaboration of workers in their examples, however, is given as an external assignment restriction and does not allow deciding on optional collaboration. Moreover, all contributions in this stream assume resource-independent processing times, i.e., a homogeneous workforce is considered. ALB problems with multi-manned stations consequently pursue determination of an advantageous amount of workers rather than the decision on their exact entities. Please note that some contributions of two-sided assembly line balancing also consider collaboration of resources on a common task (Bartholdi 1993; Gansterer and Hartl 2018; Pinnoi and Wilhelm 1997). As in multi-manned ALBP, however, these approaches propose collaboration of resources for these tasks as obligatory and do not consider this as variable. Reviews on the two-sided ALB problem are given by Abdullah Make et al. (2017) and Li et al. (2017).

The literature review indicates that recent research comprises certain characteristics required for modeling human–robot collaboration in ALB. Allocation-dependent processing times are frequently considered in RALBP and ALWABP. In contrast, planning approaches for balancing lines with multiple resources consider scheduling of tasks between the resources while task times are assumed to be independent of the resource the respective task is assigned to. None of these approaches, however, takes into account the optional collaboration of multiple resources on one task (scheduling with logical relations). This characteristic, however, is of major importance for balancing lines with collaborative robots. For that reason, we develop a novel approach for the human–robot collaborative assembly line balancing and scheduling problem (HRCALBSP) in the following.

To provide a detailed description of the problem setting we consider, a mathematical model formulation is given in this section. The assembly line consists of a given set of stations \(K\), which is connected by a material handling system, and a set \(P\) of different process alternatives is available for each task. \(P\) contains the alternatives of human (\(p_{\text{H}}\)), robotic (\(p_{\text{R}}\)), and collaborative (\(p_{\text{C}}\)) execution. Process alternatives \(p_{\text{R}} , p_{{{\text{C}} }} \in P\) require the assignment of one of \(q\) equal collaborative robots to the respective station, which is captured by the binary decision variable \(r_{k}\). A set of tasks \(I\) have to be assigned to the stations and each task \(i \in I\) requires a deterministic processing time \(t_{ip}\) depending on its process alternative \(p \in P\). The station a task is assigned to is encoded in decision variable \(z_{i}\). Whether two tasks are subject to direct precedence relations, is modeled in the corresponding set \(E\). In practice, not each task can be processed with each process alternative. To model this, \(t_{ip}\) equals a sufficiently large number if a task \(i \in I\) is considered not to be processible with the specific alternative \(p \in P\) (Levitin et al. 2006). Whether a task is assigned to a station and process alternative is indicated by the binary decision variable \(x_{ikp}\). To allow for parallel and collaborative execution, tasks are scheduled within the stations. The decision variable \(s_{i}\) represents the start time of task \(i \in I\) relative to entry of the workpiece in the respective station. The auxiliary variables \(y_{ij}\) serve to indicate whether scheduling of tasks \(\left( {i,j} \right) \in I\) is required. The decision variable \(c\) denotes the cycle time of a system configuration. The parameter \(\bar{c}\) equals the upper bound on the cycle time and is utilized as a big-M parameter in our model formulation. The used notation is summarized in Table 1.

The modeling approach is further based on the following assumptions: (i) a homogeneous product is produced. (ii) Stations are arranged serially. (iii) The necessary equipment and tools are available at each station. (iv) Processing times are deterministic, known, and constant for any process alternative. (v) The robots have limited capabilities. For instance, robotic and collaborative execution may be infeasible for certain tasks. (vi) Each task and robot can be assigned to any station and (vii) each task has to be assigned to exactly one station and process alternative. (viii) The precedence relations are known, captured in a precedence graph, and have to be respected, while (ix) no other assignment restrictions apply to the considered product.

Based on the notation and assumptions, a model formulation is derived.

Subject to:

The objective (1) is to minimize the cycle time. Constraints (2) assure that each task \(i \in I\) is assigned to exactly one station \(k \in K\) and process alternative \(p \in P\) using the binary decision variables \(x_{ikp}\). Constraint set (3) serves to define the cycle time. Constraints (4) determine the station number each task is assigned to. Constraint set (5) ensures precedence relations of tasks \(\left( {i,j} \right) \in E\), where \(i\) is a direct predecessor of \(j\). Constraints (6) and (7) ensure that both human and robot are required to perform tasks collaboratively. If a task \(i \in I\) is executed collaboratively, both human and robot are occupied with this task. Consequently, a task \(j \in I\) cannot start until \(i\) is finished. Alternatively, if task \(j \in I\) is executed collaboratively, both human and robot have to be available. Thus, a preceding task \(i \in I\) has to be finished irrespective of its processing alternative. Constraints (8) ensure that manually processed tasks \(j \in I\) can only start after the manually processed tasks \(i < j\) have been completed at the same station. The same constraint set applies to the robotic execution of two tasks \(\left( {i,j} \right) \in I\). Collaborative and robotic process alternatives are available only if robots are assigned to the respective stations. This is assured by constraint set (9). The total number of robots in the system is limited to \(q\) by constraint (10). Constraints (11) serve to determine the order of tasks within the stations. The variables are defined by constraints (12)–(15).

Our scheduling constraints extend formulations from Kim et al. (2009) and Esmaeilbeigi et al. (2016). Kim et al. consider a two-sided assembly line. In contrast, Esmaeilbeigi et al. concentrate on the setup assembly line balancing and scheduling problem. From Kim et al., we adapt the general idea of modeling the scheduling problem utilizing big-M formulations. From Esmaeilbeigi et al., we adapt the idea to encode tasks’ stations in decision variables \(z_{i}\) and to denote entry time of a workpiece in a station rather than launch time in the first station.

Since neither of the approaches are suitable to model collaborative robots’ behavior within line balancing, we explicitly model the logic relations between resources and the equipment selection problem. With our formulation, implementing the upper bound on the cycle time as a big-M parameter results in a sufficiently large number. From this, we are able to relax the big-M parameter in the scheduling constraints. \(\bar{c}\) is calculated according to the definition provided by Scholl (1999, Formula 2.63). Due to nature and assignment of the decision variables, our formulation can be classified as a MIP model.

Since the NP-hard bin packing problem can be considered as a special case of SALBP without precedence relations, SALBP is NP-hard (Álvarez-Miranda and Pereira 2019). Therefore, our generalized problem is expected to be contained in the same class. Consequently, the problem characteristics are expected to strongly influence the computational time required to solve our model. The main complexity driver of problem instances is the number of tasks (Wee and Magazine 1982; Scholl 1999, Chapter 2.2.1.5). To provide support to decision makers wavering with large problems in reasonable computational time, we develop a heuristic solution procedure for the HRCALBSP. This solution procedure is described in the following section.

Since we strive to provide a decision support system for decision makers wavering with collaborative robots’ implementation, we conduct computational experiments to examine the effectivity of our solution approaches (MIP and GA) for a variety of scenarios. Therefore, instances with realistic characteristics are constructed in Sect. 6.1. Utilizing the mathematical model, we evaluate the complexity of the introduced problem and illustrate the drivers of computational complexity in Sect. 6.2. The parametrization of the genetic algorithm and an illustration of its convergence are provided in Sect. 6.3. In Sect. 6.4, we provide a comparison of our solution approaches. Managerial insights are provided in Sect. 6.5.

The trend of increasing automation enhances the efficiency of modern manufacturing enterprises. However, certain tasks cannot efficiently be automated, for instance, due to product complexity in manufacturing corporations and small-batch production in small- and medium-sized enterprises. These challenges are predominantly faced by manual labor. In recent years, human–robot collaboration has established opportunities to increase efficiency of manual work.

Therefore, we consider the novel planning problem of configuring manual assembly lines with collaborative robots. In our balancing approach, robots can be assigned to stations to support human task execution, where both human and robotic advantages can be utilized. As robots are capable of working in collaboration with the human as well as performing tasks autonomously, the assembly line balancing problem is extended to a scheduling problem. We present a mathematical formulation to minimize assembly lines’ cycle times for a given number of stations and collaborative robots, and develop a hybrid genetic algorithm to solve the corresponding problem. In our approach, we decide about the stations the robots are assigned to and the distribution of workload among the workers and the robots. Due to the high problem complexity, only few system configurations can be determined optimally with a standard solver, which in particular holds true for large problem instances. On the contrary, the hybrid genetic algorithm allows proposing a variety of advantageous system configurations considering collaborative robots complementing workers in manual assembly lines with little computational effort.

Overall, the results indicate that substantial productivity gains can be utilized by deploying the collaborative robots. For products with 100 tasks being manufactured on an assembly line with 25 stations, deployment of 10 (5) collaborative robots may yield an average increase in productivity of 12% (7%) compared to the manual case. Due to the tradeoff between time and resource consumption of the different modes within collaborative assembly, all modes are of relevance and the actual task allocation depends heavily on the characteristics of the production system and the product structure. Therefore, line planners should carefully evaluate the production system and the product under consideration before deciding on the deployment of collaborative robots.

Further research is needed in this field. Industrial manufacturers also appreciate collaborative robots as they are able to release workers from physically stressful tasks. Consequently, aspects of ergonomics should be considered in the system configuration. Also, the determination of an economically optimal number of robots and their capabilities should be focused rather than to assume them to be given externally. Future approaches should, therefore, extend the scope of investigation and be based on multi-objective formulations considering the aspects mentioned above. Moreover, due to their object-oriented approach, the further development of genetic algorithms appears to be a promising field, particularly for multi-objective problem formulations.