A solution procedure for type E simple assembly line balancing problem

Abstract

This paper presents a type E simple assembly line balancing problem (SALBP-E) that combines models SALBP-1 and SALBP-2. Furthermore, this study develops a solution procedure for the proposed model. The proposed model provides a better understanding of management practice that optimizes assembly line efficiency while simultaneously minimizing total idle time. Computational results indicated that, under the given upper bound of cycle time (ct_max), the proposed model can solve problems optimally with minimal variables, constraints, and computing time.

Introduction

It has been over five decades since researchers first discussed the assembly line balancing problem (ALBP). Of all kinds of ALBP, the most basic is the simple assembly line balancing problem (SALBP). Bryton defined and studied SALBP as early as 1954. In the following year (1955), Salverson built the first mathematical model of SALBP and presented quantitative solving steps, which attracted great interest. After Gutjahr and Nemhauser (1964) stated that SALBP is an NP-hard combination optimization problem, the majority of researchers hoped to develop an efficient method to obtain the best solution and efficiently solve variant assembly line problems (e.g. Baybars, 1986, Boysen et al., 2007, Boysen et al., 2008, Erel and Sarin, 1998, Ghosh and Gagnon, 1989, Scholl and Becker, 2005, Scholl and Becker, 2006, Toksari et al., 2008, Yeh and Kao, 2009). During subsequent years, SALBP became a popular topic. Kim, Kim, and Kim (1996) divided SALBP into five kinds of problems, of which type I problem (SALBP-1) and type II problem (SALBP-2) are the two basic optimization problems.

Researchers have published many studies on the solution for the SALBP-1 problem. Salverson (1955) used integer programming (IP) to solve the workstation assignment problem. Jackson (1956) proposed dynamic programming (DP) to solve SALBP-1. Bowman (1960) developed two mathematical models and introduced 0–1 variables to guarantee that no tasks took the same time and that no tasks were performed at different workstations. Talbot and Patterson (1984) presented a mathematical model with a single decision variable, and used it to calculate the number of tasks assigned to workstations. Essafi, Delorme, Dolgui, and Guschinskaya (2010) proposed a mixed-integer program for solving a novel line balancing problem composed of identical CNC machines. Hackman, Magazine, and Wee (1989) used a branch and bound (BB) scheme to solve SALBP-1. To reduce the size of the branch tree, they developed heuristic depth measurement techniques that provided an efficient solution. Betts and Mahmoud, 1989, Scholl and Klein, 1997, Scholl and Klein, 1999, Ege et al., 2009 have suggested BB methods for application. Other heuristics have been developed for solving the variant problems. These may include simulated annealing (Cakir et al., 2011, Saeid and Anwar, 1997, Suresh and Sahu, 1994), Genetic Algorithm (McGovern and Gupta, 2007, Sabuncuoglu et al., 2000), and ant colony optimization algorithm (Sabuncuoglu et al., 2009, Simaria and Vilarinho, 2009). Recently, multiple-objective problems have emerged from the diversified demand of customers. For example, Rahimi-Vahed and Mirzaei (2007) proposed a hybrid multi-objective algorithm that considers the minimization of total utility work, total production rate variation, and total setup cost. Chica, Cordon, and Damas (2011) developed a model that involves the joint optimization of conflicting objectives such as the cycle time, the number of stations, and/or the area of these stations. Another interesting extension is the mixed-model problem, which is a special case of assembly line balancing problem with different models of the product allowed moving on the same line. Aimed at the mixed-model assembly line problem, Erel and Gökçen (1999) studied on mixed-model assembly line problem and established 0–1 integer programming coupled with a combined precedence diagram to reduce decision variables and constraints to increase solving efficiency. Kim and Jeong (2007) considered the problem of optimizing the input sequence of jobs in mixed-model assembly line using a conveyor system with sequence-dependent setup time. Özcan and Toklu (2009) presented a mathematical model for solving the mixed-model two-sided assembly line balancing problem with the objectives of minimizing the number of mated-stations and the number of stations for a given cycle time.

Unlike SALBP-1, the goal of SALBP-2 is to minimize cycle time given a number of workstations. Most studies focused on solutions for SALBP-1, and not SALBP-2, because SALBP-2 may be solved with SALBP-1 by gradually increasing the cycle time until the assembly line is balanced (Hackman et al., 1989). Helgeson and Bimie presented a heuristic algorithm to solve SALBP-2 as early as 1961. Scholl (1999) presented several decision problems regarding the installation and utilization of assembly line systems, indicating that balancing problem is especially important in paced assembly line cases. Scholl used task oriented BB to solve SALBP-2 and compared it with existing solution procedures. Klein and Scholl (1996) adopted new statistical methods as a solution procedure and developed a generalized BB method for directly solving SALBP-2. In addition, Gökçen and Agpak (2006) used goal programming (GP) to solve simple U-type assembly line balancing problems, in which decision makers must consider several conflicting goals at the same time. Nearchou (2007) proposed a heuristic method to solve SALBP-2 based on differential evolution (DE). In the following year, Nearchou (2008) advanced a new population heuristic method base on the multi-goal DE method to solve type II problems. Gao, Sun, Wang, and Gen (2009) presented a robotic assembly line balancing problem, in which the assembly tasks have to be assigned to workstations and each workstation needs to select one of the available robots to process the assigned tasks with the objective of minimum cycle time. Several other methods have been reported in the literature. For example, Bock (2000) proposed the Tabu Search (TS) for solving SALBP-2 and extended TS using new parallel breadth, which can be used to improve existing TS programs for assembly line problems. Levitin, Rubinovitz, and Shnits (2006) developed a genetic algorithm (GA) to solve large, complex machine assembly line balancing problems by adopting a simple principle of evolution and the BB method. A complete review of GA to assembly line balancing problems can be found in Tasan and Tunali (2008).

Most research on SALBP focuses on SALBP-1 and SALBP-2, and few studies deal with the optimization of assembly line balancing efficiency. This type of problem is called SALBP-E. This study formulates a model of SALBP-E and its solutions. SALBP-E is defined as $E=\frac{t_{\mathit{sum}}}{m·\mathit{ct}}$, and deals with assembly line balancing efficiency (E), i.e., the total time of all tasks (t_sum) divided by the number of workstations (m) multiplied by cycle time (ct). SALBP-E attempts to maximize assembly line balancing efficiency and minimize the idle time (m ⋅ ct) − t_sum. In other words, SALBP-E attempts to minimize the product of the number of workstations and cycle time.

The rest of the paper is organized as follows. Section 2 introduces SALBP-E formulation and its solution procedure. Section 3 presents solutions to a notebook computer assembly model and some test problems using small- to medium-sized for numerical calculations. Finally, this paper concludes with a summary of the approach.