{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:25:31Z","timestamp":1759667131874},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,11,18]],"date-time":"2017-11-18T00:00:00Z","timestamp":1510963200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-017-0199-9","type":"journal-article","created":{"date-parts":[[2017,11,18]],"date-time":"2017-11-18T12:50:11Z","timestamp":1511009411000},"page":"871-895","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays"],"prefix":"10.1007","volume":"36","author":[{"given":"Sven","family":"Mallach","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,18]]},"reference":[{"key":"199_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-014-0802-2","author":"A Ait El Cadi","year":"2014","unstructured":"Ait El Cadi A, Ben Atitallah R, Hanafi S, Mladenovi\u0107 N, Artiba A (2014) New MIP model for multiprocessor scheduling problem with communication delays. Optim Lett. \n                        https:\/\/doi.org\/10.1007\/s11590-014-0802-2","journal-title":"Optim Lett"},{"key":"199_CR2","unstructured":"Baxter J, Patel J (1989) The LAST algorithm\u2014a heuristic-based static task allocation algorithm. In: Proceedings of international conference on parallel processing, Pennsylvania State University, University Park, PA, USA, pp 217\u2013222"},{"key":"199_CR3","volume-title":"Scheduling theory and its applications, chap\u00a04","author":"P Chr\u00e9tienne","year":"1995","unstructured":"Chr\u00e9tienne P, Picouleau C (1995) Scheduling with communication delays: a survey. In: Chr\u00e9tienne P, Coffman EG, Lenstra JK, Liu Z (eds) Scheduling theory and its applications, chap\u00a04. Wiley, Hoboken"},{"key":"199_CR4","doi-asserted-by":"publisher","first-page":"2155","DOI":"10.1016\/j.cor.2005.01.005","volume":"33","author":"T Davidovi\u0107","year":"2006","unstructured":"Davidovi\u0107 T, Crainic TG (2006) Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems. Comput OR 33:2155\u20132177. \n                        https:\/\/doi.org\/10.1016\/j.cor.2005.01.005","journal-title":"Comput OR"},{"key":"199_CR5","unstructured":"Davidovi\u0107 T, Liberti L, Maculan N, Mladenovi\u0107 N (2004) Mathematical programming-based approach to scheduling of communicating tasks. TR G-2004-99, Montr\u00e9al, Canada"},{"key":"199_CR6","unstructured":"Davidovi\u0107 T, Liberti L, Maculan N, Mladenovi\u0107 N (2007) Towards the optimal solution of the multiprocessor scheduling problem with communication delays. In: Baptiste P, Kendall G, Munier-Kordon A, Sourd F (eds) Proceedings of 3rd multidisciplinary international conference on scheduling: theory and application, \u00c9cole Polytechnique, Paris, France, pp 128\u2013135"},{"key":"199_CR7","unstructured":"Davidovi\u0107 T, Maculan N, Mladenovi\u0107 N (2003) Mathematical programming formulation for the multiprocessor scheduling problem with communication delays. In: Proc. Simpozijum o operacionim istra\u017eivanjima (symposium on operational research), pp 331\u2013334"},{"issue":"9","key":"199_CR8","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1016\/S0167-8191(96)00041-5","volume":"22","author":"GL Djordjevi\u0107","year":"1996","unstructured":"Djordjevi\u0107 GL, To\u0161i\u0107 MB (1996) A heuristic for scheduling task graphs with communication delays onto multiprocessors. Parallel Comput 22(9):1197\u20131214. \n                        https:\/\/doi.org\/10.1016\/S0167-8191(96)00041-5","journal-title":"Parallel Comput"},{"issue":"2","key":"199_CR9","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0743-7315(90)90042-N","volume":"9","author":"H El-Rewini","year":"1990","unstructured":"El-Rewini H, Lewis TG (1990) Scheduling parallel program tasks onto arbitrary target machines. J Parallel Distrib Comput 9(2):138\u2013153. \n                        https:\/\/doi.org\/10.1016\/0743-7315(90)90042-N","journal-title":"J Parallel Distrib Comput"},{"key":"199_CR10","first-page":"17","volume":"4","author":"R Fortet","year":"1960","unstructured":"Fortet R (1960) Applications de l\u2019alg\u00e8bre de boole en recherche op\u00e9rationnelle. Revue de la Soci\u00e9t\u00e9 Fran\u00e7aise de Recherche Op\u00e9rationnelle 4:17\u201326","journal-title":"Revue de la Soci\u00e9t\u00e9 Fran\u00e7aise de Recherche Op\u00e9rationnelle"},{"issue":"1","key":"199_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0166-218X(83)90018-5","volume":"5","author":"AM Frieze","year":"1983","unstructured":"Frieze AM, Yadegar J (1983) On the quadratic assignment problem. Discrete Appl Math 5(1):89\u201398. \n                        https:\/\/doi.org\/10.1016\/0166-218X(83)90018-5","journal-title":"Discrete Appl Math"},{"issue":"3","key":"199_CR12","first-page":"503","volume":"83","author":"S Fujita","year":"2000","unstructured":"Fujita S, Yamashita M (2000) Approximation algorithms for multiprocessor scheduling problem. IEICE Trans Inform Syst 83(3):503\u2013509","journal-title":"IEICE Trans Inform Syst"},{"key":"199_CR13","doi-asserted-by":"publisher","unstructured":"Fujita S, Masukawa M, Tagashira S (2003) A fast branch-and-bound scheme for the multiprocessor scheduling problem with communication time. In: Proceedings of international conference parallel processing, IEEE, pp 104\u2013111. \n                        https:\/\/doi.org\/10.1109\/ICPPW.2003.1240360","DOI":"10.1109\/ICPPW.2003.1240360"},{"key":"199_CR14","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York"},{"key":"199_CR15","volume-title":"Multiprocessor scheduling, theory and applications, chap 4","author":"R Giroudeau","year":"2007","unstructured":"Giroudeau R, K\u00f6nig JC (2007) Scheduling with communication delays. In: Levner E (ed) Multiprocessor scheduling, theory and applications, chap 4. InTech, London"},{"key":"199_CR16","doi-asserted-by":"crossref","unstructured":"Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. In: Hammer PL, Johnson EL, Korte BH (eds) Discrete optimization II, proceedings of Advanced Research Institute on discrete optimization and systems applications of the systems science panel of NATO and the discrete optimization symposium, annals of discrete mathematics, vol\u00a05. Elsevier, pp 287\u2013326","DOI":"10.1016\/S0167-5060(08)70356-X"},{"issue":"2","key":"199_CR17","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1137\/0218016","volume":"18","author":"JJ Hwang","year":"1989","unstructured":"Hwang JJ, Chow YC, Anger FD, Lee CY (1989) Scheduling precedence graphs in systems with interprocessor communication times. SIAM J Comput 18(2):244\u2013257. \n                        https:\/\/doi.org\/10.1137\/0218016","journal-title":"SIAM J Comput"},{"key":"199_CR18","doi-asserted-by":"publisher","unstructured":"Jabrayilov A, Mallach S, Mutzel P, R\u00fcegg U, von Hanxleden R (2016) Compact layered drawings of general directed graphs. In: Hu Y, N\u00f6llenburg M (eds) 24th international symposium on graph drawing network visualization, revised selected papers, Springer, Lecture Notes in Computer Science, vol 9801, pp 209\u2013221. \n                        https:\/\/doi.org\/10.1007\/978-3-319-50106-2_17","DOI":"10.1007\/978-3-319-50106-2_17"},{"issue":"1","key":"199_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s11227-007-0139-z","volume":"43","author":"S Jin","year":"2008","unstructured":"Jin S, Schiavone G, Turgut D (2008) A performance study of multiprocessor task scheduling algorithms. J Supercomput 43(1):77\u201397. \n                        https:\/\/doi.org\/10.1007\/s11227-007-0139-z","journal-title":"J Supercomput"},{"issue":"6","key":"199_CR20","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1016\/0167-8191(94)90121-X","volume":"20","author":"D Kim","year":"1994","unstructured":"Kim D, Yi BG (1994) A two-pass scheduling algorithm for parallel programs. Parallel Comput 20(6):869\u2013885. \n                        https:\/\/doi.org\/10.1016\/0167-8191(94)90121-X","journal-title":"Parallel Comput"},{"key":"199_CR21","unstructured":"Kim SJ, Browne JC (1989) A general approach to mapping of parallel computation upon multiprocessor architectures. In: Ris F, Kogge PM (eds) Proceedings of the international conference on parallel processing, Pennsylvania State University Press, vol\u00a03, pp 1\u20138"},{"key":"199_CR22","doi-asserted-by":"publisher","unstructured":"Kong X, Sun J, Ye B, Xu W (2007) An efficient quantum-behaved particle swarm optimization for multiprocessor scheduling. In: Shi Y, van Albada GD, Dongarra J, Sloot PMA (eds) Proceedings of the 7th international conference on computational science (ICCS), part I. Springer, Berlin, pp 278\u2013285. \n                        https:\/\/doi.org\/10.1007\/978-3-540-72584-8_36","DOI":"10.1007\/978-3-540-72584-8_36"},{"key":"199_CR23","unstructured":"Kruatrachue B, Lewis TG (1987) Duplication scheduling heuristic (DSH), a new precedence task scheduler for parallel processor systems. Technical Report OR 97331, Oregon State University"},{"key":"199_CR24","doi-asserted-by":"crossref","unstructured":"Kwok YK, Ahmad I (1995) Bubble scheduling: a quasi dynamic algorithm for static allocation of tasks to parallel architectures. In: Proceedings of IEEE symposium on parallel and distributed processing, IEEE Computer Society, Washington, DC, USA, pp 36\u201343","DOI":"10.1109\/SPDP.1995.530662"},{"issue":"5","key":"199_CR25","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1109\/71.503776","volume":"7","author":"YK Kwok","year":"1996","unstructured":"Kwok YK, Ahmad I (1996) Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans Parallel Distrib Syst 7(5):506\u2013521. \n                        https:\/\/doi.org\/10.1109\/71.503776","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"4","key":"199_CR26","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1145\/344588.344618","volume":"31","author":"YK Kwok","year":"1999","unstructured":"Kwok YK, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 31(4):406\u2013471. \n                        https:\/\/doi.org\/10.1145\/344588.344618","journal-title":"ACM Comput Surv"},{"key":"199_CR27","doi-asserted-by":"publisher","unstructured":"Kwok YK, Ahmad I, Gu J (1996) FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors. In: Proceedings of international conference on parallel processing, vol\u00a02, pp 150\u2013157. \n                        https:\/\/doi.org\/10.1109\/ICPP.1996.537394","DOI":"10.1109\/ICPP.1996.537394"},{"issue":"3","key":"199_CR28","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10288-006-0015-3","volume":"5","author":"L Liberti","year":"2007","unstructured":"Liberti L (2007) Compact linearization for binary quadratic problems. 4OR 5(3):231\u2013245. \n                        https:\/\/doi.org\/10.1007\/s10288-006-0015-3","journal-title":"4OR"},{"key":"199_CR29","unstructured":"Mallach S (2016) Compact linearization for binary quadratic problems subject to assignment constraints. CoRR \n                        arXiv:1610.05375"},{"issue":"9","key":"199_CR30","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1145\/66451.66454","volume":"32","author":"C McCreary","year":"1989","unstructured":"McCreary C, Gill H (1989) Automatic determination of grain size for efficient parallel processing. Commun ACM 32(9):1073\u20131078. \n                        https:\/\/doi.org\/10.1145\/66451.66454","journal-title":"Commun ACM"},{"key":"199_CR31","doi-asserted-by":"publisher","unstructured":"Mehdiratta N, Ghose K (1994) A bottom-up approach to task scheduling on distributed memory multiprocessors. In: Proceedings of the international conference on parallel processing, vol\u00a02, pp 151\u2013154. \n                        https:\/\/doi.org\/10.1109\/ICPP.1994.14","DOI":"10.1109\/ICPP.1994.14"},{"key":"199_CR32","doi-asserted-by":"publisher","unstructured":"M\u00f6hring RH, Sch\u00e4ffter MW, Schulz AS (1996) Scheduling jobs with communication delays: using infeasible solutions for approximation (extended abstract). In: Diaz J, Serna M (eds) Proceedings of the 4th European symposium on algorithms, Springer, Berlin, LNCS, vol 1136, pp 76\u201390. \n                        https:\/\/doi.org\/10.1007\/3-540-61680-2_48","DOI":"10.1007\/3-540-61680-2_48"},{"issue":"2","key":"199_CR33","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(87)90231-6","volume":"25","author":"VJ Rayward-Smith","year":"1987","unstructured":"Rayward-Smith VJ (1987a) The complexity of preemptive scheduling given interprocessor communication delays. Inf Process Lett 25(2):123\u2013125. \n                        https:\/\/doi.org\/10.1016\/0020-0190(87)90231-6","journal-title":"Inf Process Lett"},{"issue":"1","key":"199_CR34","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0166-218X(87)90042-4","volume":"18","author":"VJ Rayward-Smith","year":"1987","unstructured":"Rayward-Smith VJ (1987b) UET scheduling with unit interprocessor communication delays. Discrete Appl Math 18(1):55\u201371. \n                        https:\/\/doi.org\/10.1016\/0166-218X(87)90042-4","journal-title":"Discrete Appl Math"},{"key":"199_CR35","volume-title":"Partitioning and scheduling parallel programs for multiprocessors","author":"V Sarkar","year":"1989","unstructured":"Sarkar V (1989) Partitioning and scheduling parallel programs for multiprocessors. MIT Press, Cambridge"},{"key":"199_CR36","doi-asserted-by":"crossref","unstructured":"Satish N, Nadathur K, Keutzer K (2007) A decomposition-based constraint optimization approach for statically scheduling task graphs with communication delays to multiprocessors. In: Proceedings of the conference on design, automation and test in Europe, EDA Consortium, San Jose, CA, USA, pp 57\u201362","DOI":"10.1109\/DATE.2007.364567"},{"issue":"8\u201310","key":"199_CR37","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S1383-7621(03)00011-0","volume":"48","author":"MA Senar","year":"2003","unstructured":"Senar MA, Ripoll A, Cort\u00e9s A, Luque E (2003) Clustering and reassignment-based mapping strategy for message-passing architectures. J Syst Archit 48(8\u201310):267\u2013283. \n                        https:\/\/doi.org\/10.1016\/S1383-7621(03)00011-0","journal-title":"J Syst Archit"},{"issue":"3","key":"199_CR38","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/s11227-010-0395-1","volume":"51","author":"AZS Shahul","year":"2010","unstructured":"Shahul AZS, Sinnen O (2010) Scheduling task graphs optimally with A*. J Supercomput 51(3):310\u2013332. \n                        https:\/\/doi.org\/10.1007\/s11227-010-0395-1","journal-title":"J Supercomput"},{"issue":"2","key":"199_CR39","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1109\/71.207593","volume":"4","author":"GC Sih","year":"1993","unstructured":"Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans Parallel Distrib Syst 4(2):175\u2013187. \n                        https:\/\/doi.org\/10.1109\/71.207593","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"199_CR40","unstructured":"Veltman B (1993) Multiprocessor scheduling with communication delays. PhD thesis, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands"},{"issue":"2","key":"199_CR41","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0167-8191(90)90056-F","volume":"16","author":"B Veltman","year":"1990","unstructured":"Veltman B, Lageweg BJ, Lenstra JK (1990) Multiprocessor scheduling with communication delays. Parallel Comput 16(2):173\u2013182. \n                        https:\/\/doi.org\/10.1016\/0167-8191(90)90056-F","journal-title":"Parallel Comput"},{"key":"199_CR42","doi-asserted-by":"publisher","unstructured":"Venugopalan S, Sinnen O (2012) Optimal linear programming solutions for multiprocessor scheduling with communication delays. In: Xiang Y, Stojmenovic I, Apduhan BO, Wang G, Nakano K, Zomaya A (eds) Proceedings of the 12th international conference on algorithms and architectures for parallel processing, part I. Springer, Berlin, pp 129\u2013138. \n                        https:\/\/doi.org\/10.1007\/978-3-642-33078-0_10","DOI":"10.1007\/978-3-642-33078-0_10"},{"issue":"1","key":"199_CR43","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1109\/TPDS.2014.2308175","volume":"26","author":"S Venugopalan","year":"2015","unstructured":"Venugopalan S, Sinnen O (2015) ILP formulations for optimal task scheduling with communication delays on parallel systems. IEEE Trans Parallel Distrib Syst 26(1):142\u2013151. \n                        https:\/\/doi.org\/10.1109\/TPDS.2014.2308175","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"199_CR44","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF00129784","volume":"2","author":"MY Wu","year":"1988","unstructured":"Wu MY, Gajski DD (1988) A programming aid for hypercube architectures. J Supercomput 2(3):349\u2013372. \n                        https:\/\/doi.org\/10.1007\/BF00129784","journal-title":"J Supercomput"},{"key":"199_CR45","doi-asserted-by":"publisher","unstructured":"Yang T, Gerasoulis A (1991) A fast static scheduling algorithm for DAGs on an unbounded number of processors. In: Proceedings of the ACM\/IEEE conference on supercomputing, ACM, New York, NY, USA, Supercomputing \u201991, pp 633\u2013642. \n                        https:\/\/doi.org\/10.1145\/125826.126138","DOI":"10.1145\/125826.126138"},{"issue":"12","key":"199_CR46","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1016\/0167-8191(93)90079-Z","volume":"19","author":"T Yang","year":"1993","unstructured":"Yang T, Gerasoulis A (1993) List scheduling with and without communication delays. Parallel Comput 19(12):1321\u20131344. \n                        https:\/\/doi.org\/10.1016\/0167-8191(93)90079-Z","journal-title":"Parallel Comput"},{"issue":"9","key":"199_CR47","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1109\/71.308533","volume":"5","author":"T Yang","year":"1994","unstructured":"Yang T, Gerasoulis A (1994) DSC: scheduling parallel tasks on an unbounded number of processors. IEEE Trans Parallel Distrib Syst 5(9):951\u2013967. \n                        https:\/\/doi.org\/10.1109\/71.308533","journal-title":"IEEE Trans Parallel Distrib Syst"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0199-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0199-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0199-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,3]],"date-time":"2018-09-03T16:59:30Z","timestamp":1535993970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0199-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,18]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["199"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0199-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,18]]}}}