{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T05:13:16Z","timestamp":1721711596243},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p> In this paper, we propose a randomized scheduling algorithm on a fully connected homogeneous multiprocessor environment. This is a randomized version of our earlier algorithm in which we used priority of modules that was dependent on the computation and the communication times associated with the modules. First we propose a generalization of our earlier scheduling algorithm with restricted number of clusters to reduce the time complexity. Then we apply randomization to the generalized algorithm and demonstrate its superiority over our previous work. We show the complexity of our proposed algorithm as O(ab |V| (|V|+|E|) log (|V|+|E|)). Here a is the number of randomization steps, and b is a limit on the number of clusters formed. If we use a and b as constants, then this gives a better complexity in comparison with the complexity of our previous algorithm that was O(|V|<jats:sup>2<\/jats:sup>(|V|+|E|) log (|V|+|E|)). In comparison with our previous work we get a performance improvement of up to 6.63% and a performance improvement of up to 12.56% when compared with Sarkar's Edge Zeroing algorithm. <\/jats:p>","DOI":"10.1142\/s0129626412500156","type":"journal-article","created":{"date-parts":[[2012,12,28]],"date-time":"2012-12-28T06:07:40Z","timestamp":1356674860000},"page":"1250015","source":"Crossref","is-referenced-by-count":5,"title":["A RANDOMIZED SCHEDULING ALGORITHM FOR MULTIPROCESSOR ENVIRONMENTS"],"prefix":"10.1142","volume":"22","author":[{"given":"PRAMOD KUMAR","family":"MISHRA","sequence":"first","affiliation":[{"name":"Department of Computer Science &amp; Department of Science and Technology, Center for Interdisciplinary Mathematical Sciences, Banaras Hindu University, Varanasi, Uttar Pradesh 221 005, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAMAL SHEEL","family":"MISHRA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, School of Management Sciences, Khushipur, Post Office Bachhaon, Varanasi, Uttar Pradesh 221 011, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ABHISHEK","family":"MISHRA","sequence":"additional","affiliation":[{"name":"Center of Excellence in Information &amp; Communication Technology, Indian Institute of Technology Rajasthan, Old Residency Road, Ratanada, Jodhpur, Rajasthan 342 011, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANIL KUMAR","family":"TRIPATHI","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering, Indian Institute of Technology (Banaras Hindu University), Varanasi, Uttar Pradesh 221 005, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,12,27]]},"reference":[{"key":"p_1","first-page":"679","volume":"199","author":"Maheswaran M.","journal-title":"New York"},{"key":"p_2","first-page":"13","volume":"26","author":"Freund R. F.","year":"1993","journal-title":"IEEE Comput."},{"key":"p_3","first-page":"1886","volume":"199","author":"Siegel H. J.","journal-title":"FL"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1109\/32.844493"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1137\/0219021"},{"key":"p_10","first-page":"83","volume":"6","author":"Mishra A.","year":"2011","journal-title":"J. Inf. Comput. Sci."},{"key":"p_11","first-page":"170","volume":"2","author":"Mishra P. K.","year":"2010","journal-title":"Int. J. Comput. Sci. Inf. Tech."},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.01.005"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626412500156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:42:41Z","timestamp":1565120561000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626412500156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":8,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,12,27]]},"published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1142\/S0129626412500156"],"URL":"https:\/\/doi.org\/10.1142\/s0129626412500156","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12]]}}}