## 1 Introduction  
For a single production line, two general groups depending on their configuration are commonly seen: traditional straight production lines and U-shaped production lines [1]. A traditional straight production line organizes the tasks sequentially in one direction to form stations [2]. A U-shaped production line, however, is divided into two sub-lines, namely, the entrance sub-line and the exit sub-line, and, thus, an operator may perform tasks on either one of the two sub-lines or on both sub-lines simultaneously [3]. In U-shaped production lines, if tasks assigned to a workstation are located in both sub-lines, then the corresponding operator has to move between the two sub-lines to perform combinations of tasks. In this case, the operator has to perform some production tasks on one workpiece in one sub-line sequentially and then pass the workpiece to the next adjacent operator. Then, the operator moves to another sub-line and works on another workpiece. A workstation that handles two workpieces in the same cycle is called a crossover station [4]. For example, in Figure 1, there are eight production tasks. Figure 1a presents a traditional straight production line. The workpieces flow from the left-hand side to the right-hand side; tasks A, B and C are assigned to workstation 1; tasks D, E and F are assigned to workstation 2; and tasks G and H are assigned to workstation 3. Figure 1b presents a U-shaped production line. Workpieces flow from the left-hand side to the right-hand side on the entrance sub-line and flow from the right-hand side to the left-hand side on the exit sub-line. The U-shaped production line provides more options for task assignment. For example, in Figure 1b, tasks A, B and H are assigned to workstation 1; tasks F and G are assigned to workstation 2; and tasks C, D and E are assigned to workstation 3. U-shaped layouts have been employed in many industries [5]. The benefits associated with U-shaped production lines include better visibility of the whole production process, more communication among operators, better teamwork, lower material handling cost, fewer operator (or workstation) requirements, higher productivity, lower work-in-process inventory, less space requirements, shorter lead time, faster response to change in market demand and motivation for a higher quality level [6; 7; 8; 9; 10]. Many studies have confirmed that the U-shaped production line balancing problem is a very significant problem for modern production systems [11]. The aim is to assign tasks to the workstations without violating any restriction [12] so that all workstations have similar amounts of work assigned to them [13]. For example, in Figure 2, there are eight production tasks. The arrows indicate the precedence relationship between a pair of tasks. The assignment of tasks to locations in a U-shaped production line has to follow the task sequence. Based on the precedence diagram, there are many feasible assignments of tasks to locations. Figure 3 provides a feasible assignment of tasks to locations based on the precedence diagram in Figure 2.  
Figure 1: An example of production types. (**a**): traditional straight production line; (**b**): U-shaped production line. Figure 3: A feasible assignment of tasks to locations. In addition to assigning tasks to locations, the assignment of tasks to workstations is also very important. It affects the amount of work in each workstation. Moreover, when assigning tasks to workstations, the locations of the tasks should be considered at the same time or the operators will get in each other's way. For example, in Figure 3, tasks A and H are assigned to workstation 1; tasks B, E and D assigned to workstation 2; and tasks C, F and G assigned to workstation 3. The result is shown in Figure 4. It can be seen that the walking paths of the operators in workstation 2 and 3 cross each other, an outcome that can be avoided if the task in location 7 is assigned to workstation 2.