Abstract

We consider a scheduling problem, which we call the scheduling and wavelength assignment (SWA) problem, arising in optical networks that are based on the wavelength-division-multiplexing (WDM) technology. We prove that the SWA problem is NP -complete for both the preemptive and the nonpreemptive cases. Furthermore, we propose two efficient approximation algorithms. The first is for the preemptive case and is based on a natural decomposition of the problem to the classical multiprocessor scheduling and open-shop problems. For the nonpreemptive case, we prove that a naive implementation of list scheduling produces a schedule that can be m times far from the optimum, where m is the number of processors (equivalently, WDM channels). Finally, we give a more refined version of list scheduling and we prove it to be a 2-approximation algorithm for both the off-line and the on-line contexts.

[IEEE ]

On Preemptive Multi-wavelength Scheduling in Hybrid WDM/TDM Passive Optical Networks

Jingjing Zhang and Nirwan Ansari
J. Opt. Commun. Netw. 4(3) 238-247 (2012)

Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective

Sahar Talebi, Evripidis Bampis, Giorgio Lucarelli, Iyad Katib, and George N. Rouskas
J. Opt. Commun. Netw. 6(8) 754-763 (2014)

Batch Scheduling in Optical Networks

Yang Wang, Xiaojun Cao, Adrian Caciula, and Qian Hu
J. Opt. Commun. Netw. 5(2) 116-126 (2013)

Minimizing Blocking Probability for the Multicast Routing and Wavelength Assignment Problem in WDM Networks: Exact Solutions and Heuristic Algorithms

Dinh Danh Le, Fen Zhou, and Miklós Molnár
J. Opt. Commun. Netw. 7(1) 36-48 (2015)

Optimal Wavelength Scheduling for Hybrid WDM/TDM Passive Optical Networks

Chonggang Wang, Wei Wei, Weiyi Zhang, Hongbo Jiang, Chunming Qiao, and Ting Wang
J. Opt. Commun. Netw. 3(6) 522-532 (2011)