Share Email Print
cover

Proceedings Paper

Scheduling problems with applications to packet-switched optical WDM networks
Author(s): Evripidis Bampis; George N. Rouskas
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

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

Paper Details

Date Published: 9 August 2001
PDF: 10 pages
Proc. SPIE 4599, OptiComm 2001: Optical Networking and Communications, (9 August 2001); doi: 10.1117/12.436056
Show Author Affiliations
Evripidis Bampis, Univ. D'Evry Val d'Essonne (France)
George N. Rouskas, North Carolina State University (United States)


Published in SPIE Proceedings Vol. 4599:
OptiComm 2001: Optical Networking and Communications

© SPIE. Terms of Use
Back to Top