|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Relocation Problems with Multiple Working Crewsстатья
- Авторы: Kononov A., Lin B.M.-T
- Журнал: Discrete Optimization
- Том: 3
- Год издания: 2006
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 366
- Последняя страница: 381
- DOI: 10.1016/j.disopt.2006.06.003
- Аннотация: The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn downand erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstructionsequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshopof makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopmentproject. Most of our results center on the situations where all buildings require the same redevelopment time. We first present astrong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of thestudied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unboundedas well as bounded numbers of machines
- Добавил в систему: Кононов Александр Вениаминович