{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T06:10:12Z","timestamp":1698041412329},"reference-count":13,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,20]],"date-time":"2006-10-20T00:00:00Z","timestamp":1161302400000},"content-version":"vor","delay-in-days":5985,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1990,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper proposes a parallel annealing algorithm, called <jats:italic>step\u2010wise\u2010overlapped parallel annealing<\/jats:italic>, that can provide a massive speed\u2010up utilizing a multiprocessor system with a large number of processors. We improve the parallel annealing scheme of the <jats:italic>systolic algorithm<\/jats:italic> that was proposed by Aart <jats:italic>et al.<\/jats:italic> Instead of the temperature decrement at each subchain, it decides the decrement ratio at the start of each Markov chain using the standard deviation of the cost distribution in the previous Markov chain of the full length. Thus the improved annealing schedule keeps a good temperature profile even with a large number of processors. We also enhance the communication pattern.<\/jats:p><jats:p>The new parallel annealing algorithm has a simple communication pattern and thus less communication overheads. The decomposition strategy of this parallel annealing algorithm is independent of application problems. Experimental results of the step\u2010wise\u2010overlapped parallel annealing algorthm for the travelling salesman problems show high efficiencies even when a large number of processors are used; it produces near optimal solutions with a speedup of 70.8 by using 128 processors. It can be implemented efficiently on a message\u2010passing multiprocessor system with a large number of processors, such as a hypercube computer.<\/jats:p>","DOI":"10.1002\/cpe.4330020204","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:07:31Z","timestamp":1163779651000},"page":"123-148","source":"Crossref","is-referenced-by-count":3,"title":["A step\u2010wise\u2010overlapped parallel annealing algorithm on a message\u2010passing multiprocessor system"],"prefix":"10.1002","volume":"2","author":[{"given":"Youngtak","family":"Kim","sequence":"first","affiliation":[]},{"given":"Myunghwan","family":"Kim","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,20]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"issue":"4","key":"e_1_2_1_3_2","first-page":"193","article-title":"Statistical cooling: a general approach to combinatorial optimization problems","volume":"40","author":"Aarts E. H. L","year":"1985","journal-title":"Philips J. Research"},{"key":"e_1_2_1_4_2","first-page":"221","article-title":"Simulated annealing without rejected moves","volume":"5","author":"Greene Jonathan W.","year":"1986","journal-title":"IEEE Trans"},{"key":"e_1_2_1_5_2","unstructured":"E. H. LAartsandP. J. Mvan Laarhoven \u2018A new polynomial time cooling schedule\u2019 inProc. Int'l Conf. on CAD 206\u2013208 1985."},{"key":"e_1_2_1_6_2","unstructured":"M. D.Huang F.RomeoandSangiovanni\u2010Vincentelli \u2018An efficient general cooling schedule for simulated annealing\u2019 Proc. Int'l Conf. on CAD 381\u2013384 1986."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(88)90037-5"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"MarkJonesandPrithvirajBanerjee \u2018Performance of a parallel algorithms for standard cell placement on the Intel hypercube\u2019 inProc. ACM\/IEEE Design Automation Conference 807\u2013813 1987.","DOI":"10.1145\/37888.38015"},{"key":"e_1_2_1_9_2","first-page":"534","article-title":"Placement by simulated annealing on a multiprocessor","volume":"6","author":"Kravitz Saul A.","year":"1987","journal-title":"IEEE Trans."},{"key":"e_1_2_1_10_2","unstructured":"EdwardFelton ScottKarlinandSteve W.Otto \u2018The travelling salesman problem on a hypercube MIMD computer\u2019 inProc. Int'l Cong. on Parallel Processing 6\u201310 1985."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(86)90002-7"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.5.495"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(87)90002-2"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330020204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330020204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:44:23Z","timestamp":1697967863000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330020204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["10.1002\/cpe.4330020204"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330020204","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}