zbMATH — the first resource for mathematics

Open block scheduling in optical communication networks. (English) Zbl 1173.68401
Jansen, Klaus (ed.) et al., Approximation and online algorithms. First international workshop, WAOA 2003, Budapest, Hungary, September 16–18, 2003. Revised papers. Berlin: Springer (ISBN 3-540-21079-2/pbk). Lecture Notes in Computer Science 2909, 13-26 (2004).
Summary: 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\| C_{\max}\) 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 \(\rho \)-approximation algorithm with \(\rho < 11/10\), unless \(\text{P}=\text{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).
For the entire collection see [Zbl 1049.68007].

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
90B18 Communication networks in operations research
90B35 Deterministic scheduling theory in operations research
Full Text: DOI