{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T14:45:45Z","timestamp":1747579545330},"reference-count":31,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,25]],"date-time":"2006-10-25T00:00:00Z","timestamp":1161734400000},"content-version":"vor","delay-in-days":4103,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The task assignment problem is one of assigning tasks of a parallel program among the processors of a distributed computing system in order to reduce the job turnaround time and to increase the throughput of the system. Since the task assignment problem is known to be NP\u2010complete except in a few special situations, satisfactory suboptimal solutions obtainable in a reasonable amount of computation time are generally sought. In the paper we introduce a technique based on the problem\u2010space genetic algorithm (PSGA) for the static task assignment problem in both homogeneous and heterogeneous distributed computing systems to reduce the task turnaround time and to increase the throughput of the system by properly balancing the load and reducing the interprocessor communication time among processors. The PSGA based approach combines the power of genetic algorithms, a global search method, with a simple and fast problem\u2010specific heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental results on test examples from the literature show considerable improvements in both the assignment cost and the CPU times over the previous work. The proposed scheme is also applied to a digital signal processing (DSP) system consisting of 119 tasks to illustrate its balancing properties and computational advantage on a large system. The proposed scheme offers 12\u201330% improvement in the assignment cost as compared to the previous best known results for the DSP example.<\/jats:p>","DOI":"10.1002\/cpe.4330070506","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T15:11:37Z","timestamp":1163776297000},"page":"411-428","source":"Crossref","is-referenced-by-count":27,"title":["Task assignment using a problem\u2010space genetic algorithm"],"prefix":"10.1002","volume":"7","author":[{"given":"Imtiaz","family":"Ahmad","sequence":"first","affiliation":[]},{"given":"Muhammad K.","family":"Dhodhi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,25]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_3_2","first-page":"85","article-title":"Multiprocessor scheduling with the aid of network flow algorithms","volume":"3","author":"Stone H. S.","year":"1977","journal-title":"IEEE Trans."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-2003-6"},{"key":"e_1_2_1_5_2","article-title":"Optimal task assignment in linear array networks","volume":"41","author":"Lee C. H.","year":"1992","journal-title":"IEEE Trans."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676563"},{"key":"e_1_2_1_7_2","first-page":"99","article-title":"On the number of acceptable task assignments in distributed computing systems","volume":"39","author":"Shin K. G.","year":"1990","journal-title":"IEEE Trans."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1980.1653419"},{"key":"e_1_2_1_9_2","unstructured":"P. Y. R.Ma E. Y. S.LeeandJ.Tsuchiya \u2018A task allocation model for distributed computing\u2019."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1982.1654050"},{"issue":"5","key":"e_1_2_1_11_2","first-page":"433","article-title":"A mapping strategy for parallel processing","volume":"36","author":"Lee S. Y.","year":"1987","journal-title":"IEEE Trans."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.207592"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.210815"},{"issue":"11","key":"e_1_2_1_14_2","first-page":"1384","article-title":"Heuristic algorithms for task assignment in distributed systems","volume":"37","author":"Lo V. M.","year":"1988","journal-title":"IEEE Trans."},{"issue":"7","key":"e_1_2_1_15_2","first-page":"699","article-title":"Module allocation of real\u2010time applications to distributed systems","volume":"16","author":"Houstis C. E.","year":"1990","journal-title":"IEEE Trans."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90024-4"},{"issue":"5","key":"e_1_2_1_17_2","first-page":"313","article-title":"Heuristic model for task allocation in distributed computer systems","volume":"138","author":"Sarje A. K.","year":"1991","journal-title":"IEE Proc. E"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.3156"},{"issue":"3","key":"e_1_2_1_19_2","first-page":"257","article-title":"On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems","volume":"41","author":"Bowen N. S.","year":"1992","journal-title":"IEEE Trans."},{"issue":"1","key":"e_1_2_1_20_2","first-page":"24","article-title":"Partitioning concurrent VLSI simulation programs on to a multiprocessor by simulated annealing","volume":"134","author":"Shield J.","year":"1987","journal-title":"IEE Proc. E"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90004-9"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-6074(93)90249-K"},{"key":"e_1_2_1_23_2","unstructured":"F. T.LinandC. C.Hsu \u2018Task assignment scheduling by simulated annealing \u2019IEEE Region 10 Conference on Computer and Communication Systems Hong Kong September1990 pp.279\u2013283."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90013-D"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(92)90062-C"},{"key":"e_1_2_1_26_2","volume-title":"Adaption in Natural and Artificial Systems","author":"Holland J. H.","year":"1975"},{"key":"e_1_2_1_27_2","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"Goldberg D. E.","year":"1989"},{"key":"e_1_2_1_28_2","first-page":"500","article-title":"A genetic approach to standard cell placement using metagenetic parameter optimization","volume":"9","author":"Shahookar K.","year":"1990","journal-title":"IEEE Trans."},{"key":"e_1_2_1_29_2","volume-title":"Handbook of Genetic Algorithms","author":"Davis L.","year":"1991"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02830-8"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.38.10.1495"},{"key":"e_1_2_1_32_2","unstructured":"Muhammad K.Dhodhi Data Path Synthesis Using Concurrent Scheduling and Allocation Based on Problem\u2010Space Genetic Algorithms PhD dissertation Department of Electrical Engineering and Computer Science Lehigh University Bethlehem PA August1992."}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330070506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330070506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T17:05:26Z","timestamp":1698339926000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330070506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1002\/cpe.4330070506"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330070506","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}