|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Open Block Scheduling in Optical Communication Networksстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Ageev A., Fishkin A., Kononov A., Sevastianov S.
- Журнал: Theoretical Computer Science
- Том: 361
- Год издания: 2006
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 257
- Последняя страница: 274
- DOI: 10.1016/j.tcs.2006.05.014
- Аннотация: In this paper the process of data transmission in star coupled optical communication networks is modelled as a shop-type scheduling problem, where channels (wavelengths) are treated as machines. We formulate an Open Block problem with the minimum makespan objective (OB||Cmax) in which a relation of a new type between the operations of each job is introduced: any two operations of a job have identical processing times and may be processed either simultaneously (in a common block) or, alternatively, at disjointtime intervals. We show that the problem is polynomially solvable for 4 machines, NP-hard for 6 machines and strongly NP-hardfor a variable number of machines. For the case of a variable number of machines we present a polynomial time √2-approximationalgorithm and prove that there is no polynomial time -approximation algorithm with < 11/10, unless P = NP. For the case when the number of machines is fixed, we show that the problem admits a linear time PTAS. In addition, we show that the two-machineproblem with release dates is NP-hard in the strong sense.
- Добавил в систему: Кононов Александр Вениаминович