# 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.