%0 Journal Article %1 birmpilis2017critical %A Birmpilis, Stavros %A Aslanidis, Timotheos %D 2017 %E Meghanathan, Natarajan %J International Journal of Computer Networks & Communications (IJCNC) %K Interconnection,scheduling, approximation preemption, %N 1 %P 1-11 %T A Critical Improvement on Open Shop Scheduling Algorithm for Routing in Interconnection Networks %U http://aircconline.com/ijcnc/V9N1/9117cnc01.pdf %V 9 %X In the past years, Interconnection Networks have been used quite often and especially in applications where parallelization is critical. Message packets transmitted through such networks can be interrupted using buffers 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 topology reconfiguration and consequently 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 haveimproved, critically, variations of polynomially solvable instances of Open Shop to approximate PBS. We have combined these variations and called the induced algorithmI_HSA (Improved Hybridic Scheduling Algorithm). We ran experiments to establish the efficiency of I_HSA and found that in all datasets used it produces schedules very close to the optimal. In addition, we tested I_HSA with datasets that follow non-uniform distributions and provided statistical data which illustrates better its performance.To further establish I_HSA’s efficiency we ran tests to compare it to SGA, another algorithm which when tested in the past has yielded excellent results

@article{birmpilis2017critical, abstract = {In the past years, Interconnection Networks have been used quite often and especially in applications where parallelization is critical. Message packets transmitted through such networks can be interrupted using buffers 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 topology reconfiguration and consequently 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 haveimproved, critically, variations of polynomially solvable instances of Open Shop to approximate PBS. We have combined these variations and called the induced algorithmI_HSA (Improved Hybridic Scheduling Algorithm). We ran experiments to establish the efficiency of I_HSA and found that in all datasets used it produces schedules very close to the optimal. In addition, we tested I_HSA with datasets that follow non-uniform distributions and provided statistical data which illustrates better its performance.To further establish I_HSA’s efficiency we ran tests to compare it to SGA, another algorithm which when tested in the past has yielded excellent results}, added-at = {2017-02-01T02:40:30.000+0100}, author = {Birmpilis, Stavros and Aslanidis, Timotheos}, biburl = {https://www.bibsonomy.org/bibtex/224ba8d3ce96e36604055116945bfd745/laimbee}, editor = {Meghanathan, Natarajan}, interhash = {127a33d80dd4c370b7d17275769e2d34}, intrahash = {24ba8d3ce96e36604055116945bfd745}, journal = {International Journal of Computer Networks & Communications (IJCNC) }, keywords = {Interconnection,scheduling, approximation preemption,}, month = {Jansuary}, number = 1, pages = {1-11}, timestamp = {2017-02-01T02:40:30.000+0100}, title = {A Critical Improvement on Open Shop Scheduling Algorithm for Routing in Interconnection Networks}, url = {http://aircconline.com/ijcnc/V9N1/9117cnc01.pdf}, volume = 9, year = 2017 }