18336

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Доклад

Название: 

Some Complexity Results for the Simple Assembly Line Balancing Problem

ISBN/ISSN: 

978-5-91601-069-5

Наименование конференции: 

  • III International Conference on Optimization Methods and Application (OPTIMA-2012), Costa da Caparica, Portugal, september 2012

Наименование источника: 

  • Proceedings of the III International Conference on Optimization Methods and Application (OPTIMA-2012,Costa da Caparica, Portugal)

Город: 

  • Москва

Издательство: 

  • Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А.А.Дородницына РАН

Год издания: 

2012

Страницы: 

81-85
Аннотация
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.

Библиографическая ссылка: 

Гафаров Е.Р., Долгий А.Б., Лазарев А.А. Some Complexity Results for the Simple Assembly Line Balancing Problem / Proceedings of the III International Conference on Optimization Methods and Application (OPTIMA-2012,Costa da Caparica, Portugal). М.: Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А.А.Дородницына РАН, 2012. С. 81-85.