{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,3,4]],"date-time":"2023-03-04T22:30:23Z","timestamp":1677969023607},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p> We consider the problem of scheduling an application on a parallel computational platform. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified. It is also subject to failures: if a processor is slowed down to decrease the energy consumption, it has a higher chance to fail. Therefore, the scheduling problem requires us to re-execute or replicate tasks (i.e., execute twice the same task, either on the same processor, or on two distinct processors), in order to increase the reliability. It is a tri-criteria problem: the goal is to minimize the energy consumption, while enforcing a bound on the total execution time (the makespan), and a constraint on the reliability of each task. Our main contribution is to propose approximation algorithms for linear chains of tasks and independent tasks. For linear chains, we design a fully polynomial-time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we propose in this case an approximation algorithm with a relaxation on the makespan constraint. <\/jats:p>","DOI":"10.1142\/s0129626416500018","type":"journal-article","created":{"date-parts":[[2016,3,28]],"date-time":"2016-03-28T02:05:18Z","timestamp":1459130718000},"page":"1650001","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Energy, Reliability, and Makespan Optimization Problems"],"prefix":"10.1142","volume":"26","author":[{"given":"Guillaume","family":"Aupy","sequence":"first","affiliation":[{"name":"LIP \u2013 ENS Lyon, 46 All\u00e9e d\u2019Italie, 69364 Lyon Cedex 07, France"}]},{"given":"Anne","family":"Benoit","sequence":"additional","affiliation":[{"name":"LIP \u2013 ENS Lyon, 46 All\u00e9e d\u2019Italie, 69364 Lyon Cedex 07, France"}]}],"member":"219","published-online":{"date-parts":[[2016,3,27]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1145\/1735223.1735245"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-013-0312-6"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206038"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2005.859474"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568525"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1261830"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9070-1"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1236-4"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1109\/24.24570"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626416500018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:29:55Z","timestamp":1565080195000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626416500018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2016,3,27]]},"published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.1142\/S0129626416500018"],"URL":"https:\/\/doi.org\/10.1142\/s0129626416500018","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3]]}}}