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].
Document type :
Conference papers
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-00733610
Contributor : Florent Breuil <>
Submitted on : Wednesday, September 19, 2012 - 9:53:17 AM
Last modification on : Thursday, October 17, 2019 - 12:36:12 PM

Identifiers

  • HAL Id : emse-00733610, version 1

Citation

Evgeny R. Gafarov, Alexandre Dolgui, Alexander Lazarev. Some Complexity Results for the Simple Assembly Line Balancing Problem. III International conference Optimization and applications, Sep 2012, Costa da Caparica, Portugal. pp 81-85. ⟨emse-00733610⟩

Share

Metrics

Record views

184