Scheduling problems with applications to packet-switched optical WDM networks

Evripidis Bampis; George N. Rouskas

doi:10.1117/12.436056

9 August 2001 Scheduling problems with applications to packet-switched optical WDM networks

Evripidis Bampis, George N. Rouskas

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.

Citation Download Citation

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

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available