Title: An open shop approach in approximating optimal data transmission duration in WDM networks,
Abstract: 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 HSAs efficiency we ran tests to compare it to
SGA, another algorithm which when tested in the past has yielded excellent
results.