## 2 A Division of Manual Labor, Assembly and Production Lines
### Generalizations of the SALBP and Complexity of These Problems  
The OR literature contains investigations of different formulations of the ALBP that result from the weakening of one or more conditions, (A-1)-(A-9). An assembly line can be used to produce several modifications of a product that are divided into batches. Such assembly lines are called multi-model lines. The assembly line can be used to produce two or more modifications of the same product. Different modifications of the product can be mixed in the process of their assembly. Such assembly lines in the OR literature are called mixed-model assembly lines [26; 27; 28; 29]. Assembly line configurations can vary. In particular, article [27] discusses a U-shaped assembly line for a mixed-model ALBP. In articles [10; 29; 30; 31; 32; 33], the SALBP is considered for a two-way assembly line, when workstations are located on both sides of a linear or U-shaped conveyor belt. The assembly line may have parallel workstations that may duplicate one another in the event of a workstation breakdown [34; 35]. Other generalizations of the simple assembly line balancing problem can be found in [36; 37]. No matter what goal is considered in the problem (minimizing cycle time, \(C\), minimizing the number of workstations or maximizing the efficiency, \(E\)), generalized assembly line balancing problems are called general assembly line balancing problems [38]. Thus, the GALBP can denote a generalization of the SALBP-1, the SALBP-2 or the SALBP-E. It should be noted that <<simple>> SALBP-1, SALBP-2 and SALBP-E are in fact binary NP-hard even in the simplest possible case, i.e., when \(m=2\) and the given precedence digraph \(G=(V,A)\) does not contain any arc, \(A=\)O (it is clear that there is no conveyer with \(m=1\)). Thus, one could use the term <<ideal>> instead of <<simple>> for the NP-hard SALBP. The proof of the NP-hardness of the SALBP-1, SALBP-2 and SALBP-E follows from the fact that the binary NP-hard scheduling problem, \(I2||C_{\max}\) (see monographs in [39; 40] on scheduling theory), is reduced in a polynomial number of elementary operations to a determined special case of the SALBP, namely: SALBP-1, SALBP-2 and SALBP-E. Hereafter, a three-field notation, \(\alpha|\beta|\gamma\), is used to denote a scheduling problem, in which \(\alpha\) indicates the type of processing system, \(\beta\) denotes specified restrictions on the set of jobs to be processed and \(\gamma\) denotes the criterion of optimality (see [41]). In particular, in the problem \(I2||C_{\max}\), it is necessary to construct a schedule with minimum schedule length \(C_{\max}\) for fulfilling a given set of jobs on two identical machines. The proof of the NP-hardness of the SALBP can be found in the monograph [4]. Before starting the survey section, it would be useful to explain why the remaining Sections 3-7 are mainly devoted to the SALBP. Note that a simple assembly line balancing problem may be rarely met in real-world productions, since the most practical assembly lines violate some or most conditions of (A-1)-(A-11). On the other hand, the most final mathematical results (lemmas and theorems) have been proven only for the SALBP-1, SALBP-2 and SALBP-E. Furthermore, these mathematical results may be used for real assembly and production lines. Due to the limited paper length, the proven mathematical claims are not presented in Sections 3-7 (they are only mentioned in their descriptions). Hopefully, increasing the uncertainty level in the considered ALBP may be useful for constructing a bridge between the ideal SALBP and practical assembly and production lines. Deterministic Problems of Designing and Balancing Assembly Lines with Deviations from Normally Fixed Conditions  
If the condition (A-1) for the ALBP is met with a possible change in the other conditions, (A-2)-(A-9), and then such a problem is called a deterministic ALBP. For the deterministic ALBP, the durations of assembly operations, \(t_{i},i\in V\), are given and do not change during the whole lifecycle of the assembly conveyer.