|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirementsстатья
- Авторы: Gu H., Kononov A., Memar J., Zinder Y.
- Журнал: Journal of Discrete Algorithms
- Том: 52
- Год издания: 2018
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 143
- Последняя страница: 155
- DOI: 10.1016/j.jda.2018.11.011
- Аннотация: The paper is concerned with minimisation of the total weighted completion time for thetwo-stage flow shop with a buffer. In contrast to the vast literature on this topic, thebuffer requirement varies from job to job and a job occupies the buffer continuouslyfrom the start of its first operation till the completion of its second operation ratherthan only between operations. Such problems arise in supply chains requiring unloadingand loading of minerals and in some multimedia systems. The problem is NP-hard inthe strong sense, and we prove that if the order of jobs is fixed for one of the stages,then even for the criteria of the maximum completion time or the total completion timethe problem remains NP-hard in the strong sense. Straightforward integer programmingapproach is impossible even for modest problem sizes. The paper presents a Lagrangianrelaxation based decomposition approach that allows to use for each problem, obtained bythis decomposition, a very fast algorithm. Several Lagrangian heuristics are evaluated bymeans of computational experiments.
- Добавил в систему: Кононов Александр Вениаминович