Translator Disclaimer
9 August 2001 Scheduling problems with applications to packet-switched optical WDM networks
Author Affiliations +
Proceedings Volume 4599, OptiComm 2001: Optical Networking and Communications; (2001) https://doi.org/10.1117/12.436056
Event: OptiComm 2001: Optical Networking and Communications Conference, 2001, Denver, CO, United States
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 (Nu) (Rho) -hard for both the preemptive and the non- preemptive cases. Furthermore, we propose two efficient approximation algorithms. The first is for the preemptive case and it is based on a natural decomposition of the problem to the classical multiprocessor scheduling and open-shop problems. For the non-preemptive 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.
© (2001) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Evripidis Bampis and George N. Rouskas "Scheduling problems with applications to packet-switched optical WDM networks", Proc. SPIE 4599, OptiComm 2001: Optical Networking and Communications, (9 August 2001); https://doi.org/10.1117/12.436056
PROCEEDINGS
10 PAGES


SHARE
Advertisement
Advertisement
Back to Top