Some Complexity Results for the Simple Assembly Line Balancing Problem - Mines Saint-Étienne
Conference Papers Year : 2012

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].
No file

Dates and versions

emse-00733610 , version 1 (19-09-2012)

Identifiers

  • HAL Id : emse-00733610 , version 1

Cite

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⟩
119 View
0 Download

Share

More