|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Some Complexity Results for the Simple Assembly Line Balancing Problemтезисы доклада
- Авторы: Гафаров Е.Р., Долгий А.Б., Лазарев А.А.
- Сборник: Сборник трудов III Международной конференции "Оптимизация и приложения" (ОПТИМА-2012). Costa da Caparica, Portugal, september 2012
- Тезисы
- Год издания: 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.
- Добавил в систему: Лазарев Александр Алексеевич