{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:28:50Z","timestamp":1649179730031},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p> The goal of this work is to study the portfolio problem which consists in finding a good combination of multiple heuristics given a set of a problem instances to solve. We are interested in a parallel context where the resources are assumed to be discrete and homogeneous, and where it is not possible to allocate a given resource (processor) to more than one heuristic. The objective is to minimize the average completion time over the whole set of instances. We extend in this paper some existing analysis on the problem. More precisely, we provide a new complexity result for the restricted version of the problem, then, we generalize previous approximation schemes. In particular, they are improved using a guess approximation technique. Experimental results are also provided using a benchmark of instances on SAT solvers. <\/jats:p>","DOI":"10.1142\/s0129054111008271","type":"journal-article","created":{"date-parts":[[2011,4,18]],"date-time":"2011-04-18T10:11:52Z","timestamp":1303121512000},"page":"639-656","source":"Crossref","is-referenced-by-count":3,"title":["APPROXIMATING THE DISCRETE RESOURCE SHARING SCHEDULING PROBLEM"],"prefix":"10.1142","volume":"22","author":[{"given":"MARIN","family":"BOUGERET","sequence":"first","affiliation":[{"name":"LIG, Grenoble University, 51 avenue J. Kuntzmann, 38330 Montbonnot, France"}]},{"given":"PIERRE-FRAN\u00c7OIS","family":"DUTOT","sequence":"additional","affiliation":[{"name":"LIG, Grenoble University, 51 avenue J. Kuntzmann, 38330 Montbonnot, France"}]},{"given":"ALFREDO","family":"GOLDMAN","sequence":"additional","affiliation":[{"name":"LIG, Grenoble University, 51 avenue J. Kuntzmann, 38330 Montbonnot, France"}]},{"given":"YANIK","family":"NGOKO","sequence":"additional","affiliation":[{"name":"LIG, Grenoble University, 51 avenue J. Kuntzmann, 38330 Montbonnot, France"}]},{"given":"DENIS","family":"TRYSTRAM","sequence":"additional","affiliation":[{"name":"LIG, Grenoble University, 51 avenue J. Kuntzmann, 38330 Montbonnot, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009158"},{"key":"rf2","first-page":"193","author":"An P.","journal-title":"Lecture notes in computer science"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1147\/rd.502.0223"},{"key":"rf11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00081-3"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1126\/science.275.5296.51"},{"key":"rf14","first-page":"5","author":"Markowitz H.","journal-title":"Financial Analysts Journal"},{"key":"rf16","author":"Schuurman P.","journal-title":"Lectures on Scheduling"},{"key":"rf17","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"Shachnai H.","year":"2007"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(04)00318-X"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009669824615"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235820"},{"key":"rf23","first-page":"106","author":"Zheng F.","journal-title":"Information Processing Letters"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111008271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:23:20Z","timestamp":1565191400000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111008271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1142\/S0129054111008271"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111008271","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4]]}}}