|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Open Block Scheduling in Optical Communication Networkтезисы доклада
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Ageev A., Fishkin A., Kononov A., Sevastianov S.
- Сборник: Approximation and Online Algorithms. WAOA 2003
- Серия: Lecture Notes in Computer Science
- Том: 2909
- Тезисы
- Год издания: 2004
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 13
- Последняя страница: 26
- DOI: 10.1007/978-3-540-24592-6_2
- Аннотация: In this paper the process of data transmission in optical communication networks is modeled as a shop-type scheduling problem, where channels (wavelengths) are treated as machines. We formulate an Open Block problem with the minimum makespan objective (an OB||Cmax problem) 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 completely simultaneously (in a common block) or, alternatively, with full diversity in time. We show that the problem is polynomially solvable for 4 machines, binary NP-hard for 6 machines and strongly NP-hard for a variable number of machines. Adding release dates to the two-machine problem also leads to the NP-hardness in strong sense. For the case of a variable number of machines we present a polynomial time (sqrt 2)-approximation algorithm 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 can be solved by a linear time PTAS and by a few linear time statistically optimal algorithms (generating optimal schedules for almost all instances).
- Добавил в систему: Кононов Александр Вениаминович