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].

For the entire collection see [Zbl 1049.68007].

##### MSC:

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 |