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].
Type de document :
Communication dans un congrès
V.I. Zubov. III International conference Optimization and applications, Sep 2012, Costa da Caparica, Portugal. pp 81-85, 2012
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00733610
Contributeur : Florent Breuil <>
Soumis le : mercredi 19 septembre 2012 - 09:53:17
Dernière modification le : mardi 23 octobre 2018 - 14:36:09

Identifiants

  • HAL Id : emse-00733610, version 1

Citation

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

Partager

Métriques

Consultations de la notice

173