In the past decade Optical WDM Networks (Wavelength Division Multiplexing) are being used
quite often and especially as far as broadband applications are concerned. Message packets
transmitted through such networks can be interrupted using time slots in order to maximize
network usage and minimize the time required for all messages to reach their destination.
However, preempting a packet will result in time cost. The problem of scheduling message
packets through such a network is referred to as PBS and is known to be NP-Hard. In this paper
we have reduced PBS to Open Shop Scheduling and designed variations of polynomially
solvable instances of Open Shop to approximate PBS. We have combined these variations and
called the induced algorithm HSA (Hybridic Scheduling Algorithm). We ran experiments to
establish the efficiency of HSA and found that in all datasets used it produces schedules very
close to the optimal. To further establish HSA’s efficiency we ran tests to compare it to SGA,
another algorithm which when tested in the past has yielded excellent results.