ИСТИНА

We consider the simple assembly line balancing problem (SALBP-1) which is formulated as follows. Given a set $N=\{1, 2, \dots,n\}$ of operations and $K$ stations (machines) $1,2,\dots,K$. For each operation $j\in N$ a processing time $t_j\geq 0$ is defined. The cycle time $c\geq \max\{t_j,\ j\in N\}$ is given. Furthermore, finish-start precedence relations $i \rightarrow j$ are defined between the operations according to an acyclic directed graph $G.$ The objective is to assign each operation $j, \; j=1, 2, \dots,n,$ to a station in such a way that: - number $m\leq M$ of stations used is minimized; - for each station $k = 1,2,\dots,m$ a total load time $\sum_{j \in N_k}t_j$ does not exceed $c$, where $N_k$ -- a set of operations assigned to a station $k$; - given precedence relations are fulfilled, i.e. if $i\rightarrow j,\ i \in N_{k_1}$ and $j \in N_{k_2}$ then $k_1\leq k_2$. A survey on results for NP-hard in the strong sense SALBP-1 is presented.