Some Complexity Results for the Simple Assembly Line Balancing Problem
Abstract
We consider the simple assembly line balancing problem (SALBP-1) which is formulated as follows. Given a set N = {1, 2, . . . , n} of operations and K stations (machines) 1, 2, . . . ,K. For each operation j ∈ N a processing time tj ≥ 0 is defined. The cycle time c ≥ max{tj , j ∈ N} is given. Furthermore, finish-start precedence relations i → j are defined between the operations according to an acyclic directed graph G. The objective is to assign each operation j, j = 1, 2, . . . , n, to a station in such a way that: - number m ≤ M of stations used is minimized; - for each station k = 1, 2, . . . ,m a total load time Pj∈Nk tj does not exceed c, where Nk - a set of operations assigned to a station k; - given precedence relations are fulfilled, i.e. if i → j, i ∈ Nk1 and j ∈ Nk2 then k1 ≤ k2. A survey on results for NP-hard in the strong sense SALBP-1 is pre- sented, e.g., in [1,2].