{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,22]],"date-time":"2024-06-22T10:31:45Z","timestamp":1719052305297},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,8,12]],"date-time":"2010-08-12T00:00:00Z","timestamp":1281571200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00224-010-9250-2","type":"journal-article","created":{"date-parts":[[2010,8,11]],"date-time":"2010-08-11T04:25:24Z","timestamp":1281500724000},"page":"856-877","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Multiprocessor Scheduling under Uncertainty"],"prefix":"10.1007","volume":"47","author":[{"given":"Guolong","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,12]]},"reference":[{"issue":"2","key":"9250_CR1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1287\/ijoc.3.2.149","volume":"3","author":"D. Applegate","year":"1991","unstructured":"Applegate, D., Cook, B.: A\u00a0computational study of the job-shop scheduling problem. ORSA J. Comput. 3(2), 149\u2013156 (1991)","journal-title":"ORSA J. Comput."},{"key":"9250_CR2","volume-title":"Introduction to Linear Optimization","author":"D. Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Nashua (1997)"},{"key":"9250_CR3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493\u2013509 (1952)","journal-title":"Ann. Math. Stat."},{"key":"9250_CR4","doi-asserted-by":"crossref","unstructured":"Chudak, F., Shmoys, D.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms 30 (1999)","DOI":"10.1006\/jagm.1998.0987"},{"key":"9250_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill, Cambridge (2001)","edition":"2"},{"key":"9250_CR6","doi-asserted-by":"crossref","unstructured":"Crutchfield, C., Dzunic, Z., Fineman, J., Karger, D., Scott, J.: Improved approximations for multiprocessor scheduling under uncertainty. In: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Munich, Germany, pp.\u00a0246\u2013255 (2008)","DOI":"10.1145\/1378533.1378579"},{"key":"9250_CR7","doi-asserted-by":"crossref","unstructured":"Fernandez, A., Armacost, R., Pet-Edwards, J.: A model for the resource constrained project scheduling problem with stochastic task durations. In: 7th Industrial Engineering Research Conference Proceedings (1998)","DOI":"10.1080\/10429247.1998.11415002"},{"issue":"4","key":"9250_CR8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1080\/10429247.1998.11415002","volume":"10","author":"A. Fernandez","year":"1998","unstructured":"Fernandez, A., Armacost, R., Pet-Edwards, J.: Understanding simulation solutions to resource constrained project scheduling problems with stochastic task durations. Eng. Manag. J. 10(4), 5\u201313 (1998)","journal-title":"Eng. Manag. J."},{"key":"9250_CR9","volume-title":"Flows in Networks","author":"L.R. Ford Jr.","year":"1962","unstructured":"Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"9250_CR10","volume-title":"The Grid: Blueprint for a New Computing Infrastructure","year":"2004","unstructured":"Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure, 2nd edn. Morgan Kaufmann, San Francisco (2004)","edition":"2"},{"key":"9250_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H.\u00a0Freeman, San Francisco (1979)"},{"key":"9250_CR12","doi-asserted-by":"crossref","unstructured":"Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999)","DOI":"10.1109\/SFFCS.1999.814632"},{"key":"9250_CR13","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. (BSTJ) 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J. (BSTJ)"},{"key":"9250_CR14","volume-title":"Approximation Algorithms for NP-hard Problems","author":"L. Hall","year":"1997","unstructured":"Hall, L.: Approximation algorithms for scheduling. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems. PWS, Boston (1997)"},{"issue":"2","key":"9250_CR15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.ejor.2004.04.002","volume":"165","author":"W. Herroelen","year":"2005","unstructured":"Herroelen, W., Leus, R.: Project scheduling under uncertainty: Survey and research potentials. Eur. J. Oper. Res. 165(2), 289\u2013306 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"9250_CR16","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1214\/aoms\/1177728178","volume":"27","author":"W. Hoeffding","year":"1956","unstructured":"Hoeffding, W.: On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27, 713\u2013721 (1956)","journal-title":"Ann. Math. Stat."},{"key":"9250_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM J. Comput. 30 (2000)","DOI":"10.1137\/S0097539797329142"},{"key":"9250_CR18","doi-asserted-by":"crossref","unstructured":"Kumar, V., Marathe, M., Parthasarathy, S., Srinivasan, A.: Scheduling on unrelated machines under tree-like precedence constraints. In: International Workshop on Approximation Algorithms for Combinatorial Optimization (2005)","DOI":"10.1007\/11538462_13"},{"key":"9250_CR19","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.R., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam (1991)"},{"issue":"2","key":"9250_CR20","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F.T. Leighton","year":"1994","unstructured":"Leighton, F.T., Maggs, B.M., Rao, S.: Packet routing and job-shop scheduling in O (congestion + dilation) steps. Combinatorica 14(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"key":"9250_CR21","doi-asserted-by":"crossref","unstructured":"Lenstra, J., Shmoys, D., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46 (1990)","DOI":"10.1007\/BF01585745"},{"key":"9250_CR22","doi-asserted-by":"crossref","unstructured":"Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. In: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 25\u201334, San Diego, CA, USA (2007)","DOI":"10.1145\/1248377.1248383"},{"key":"9250_CR23","doi-asserted-by":"crossref","unstructured":"Lin, G., Rajaraman, R.: Approximation algorithms for multiprocessor scheduling under uncertainty. Technical report, March 2007. arXiv:cs\/0703100v1","DOI":"10.1145\/1248377.1248383"},{"key":"9250_CR24","doi-asserted-by":"crossref","unstructured":"Malewicz, G.: Parallel scheduling of complex dags under uncertainty. In: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 66\u201375, Las Vegas, Nevada, USA (2005)","DOI":"10.1145\/1073970.1073981"},{"key":"9250_CR25","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M. Pinedo","year":"2002","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs (2002)"},{"key":"9250_CR26","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988)","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"9250_CR27","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Thompson, C.: Provably good routing in graphs: Regular arrays. In: ACM Symposium on Theory of Computing (STOC) (1985)","DOI":"10.1145\/22145.22154"},{"key":"9250_CR28","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Thompson, C.: Randomized rounding: A\u00a0technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987)","DOI":"10.1007\/BF02579324"},{"key":"9250_CR29","doi-asserted-by":"crossref","unstructured":"Schmidt, J., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8 (1995)","DOI":"10.1137\/S089548019223872X"},{"key":"9250_CR30","series-title":"Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1986)"},{"key":"9250_CR31","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23 (1994)","DOI":"10.1137\/S009753979222676X"},{"issue":"2","key":"9250_CR32","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M. Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite programming relaxations in scheduling. J. Assoc. Comput. Mach. (JACM) 48(2), 206\u2013242 (2001)","journal-title":"J. Assoc. Comput. Mach. (JACM)"},{"key":"9250_CR33","unstructured":"Skutella, M., Uetz, M.: Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 589\u2013590, Washington, DC, USA (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9250-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9250-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9250-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T15:48:30Z","timestamp":1559404110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9250-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9250"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9250-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,12]]}}}