{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T09:09:40Z","timestamp":1771232980146,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71871203"],"award-info":[{"award-number":["71871203"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["51305400"],"award-info":[{"award-number":["51305400"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY18G010017"],"award-info":[{"award-number":["LY18G010017"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s10479-019-03346-4","type":"journal-article","created":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T12:02:36Z","timestamp":1564142556000},"page":"397-425","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A new approximation algorithm for unrelated parallel machine scheduling with release dates"],"prefix":"10.1007","volume":"285","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6808-1490","authenticated-orcid":false,"given":"Zhi","family":"Pei","sequence":"first","affiliation":[]},{"given":"Mingzhong","family":"Wan","sequence":"additional","affiliation":[]},{"given":"Ziteng","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"key":"3346_CR1","doi-asserted-by":"publisher","unstructured":"Arnaout, J.-P. (2019). A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. Annals of Operations Research, 1\u201321. \nhttps:\/\/doi.org\/10.1007\/s10479-019-03138-w\n\n.","DOI":"10.1007\/s10479-019-03138-w"},{"issue":"1","key":"3346_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0377-2217(97)00427-X","volume":"113","author":"M Azizoglu","year":"1999","unstructured":"Azizoglu, M., & Kirca, O. (1999a). On the minimization of total weighted flow time with identical and uniform parallel machines. European Journal of Operational Research, 113(1), 91\u2013100.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"3346_CR3","first-page":"153","volume":"31","author":"M Azizoglu","year":"1999","unstructured":"Azizoglu, M., & Kirca, O. (1999b). Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE Transactions, 31(2), 153\u2013159.","journal-title":"IIE Transactions"},{"key":"3346_CR4","unstructured":"Balas, E., Ceria, S., Cornuejols, G., & Pataki, G. (1994). Updated semi-definite constraints. Tech. rep.: Technical Report, Carnegie Mellon University, Pittsburgh, USA."},{"issue":"1\u20134","key":"3346_CR5","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1080\/10556789908805765","volume":"11","author":"B Borchers","year":"1999","unstructured":"Borchers, B. (1999). Csdp, ac library for semidefinite programming. Optimization Methods and Software, 11(1\u20134), 613\u2013623.","journal-title":"Optimization Methods and Software"},{"issue":"4","key":"3346_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s10951-016-0485-x","volume":"20","author":"K B\u00fclb\u00fcl","year":"2017","unstructured":"B\u00fclb\u00fcl, K., & \u015een, H. (2017). An exact extended formulation for the unrelated parallel machine total weighted completion time problem. Journal of Scheduling, 20(4), 373\u2013389.","journal-title":"Journal of Scheduling"},{"issue":"6","key":"3346_CR7","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1007\/s10845-013-0842-y","volume":"26","author":"J Chen","year":"2015","unstructured":"Chen, J. (2015). Unrelated parallel-machine scheduling to minimize total weighted completion time. Journal of Intelligent Manufacturing, 26(6), 1099\u20131112.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"1","key":"3346_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1287\/ijoc.11.1.78","volume":"11","author":"Z Chen","year":"1999","unstructured":"Chen, Z., & Powell, W. B. (1999). Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11(1), 78\u201394.","journal-title":"INFORMS Journal on Computing"},{"key":"3346_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jmsy.2016.10.005","volume":"42","author":"C Cheng","year":"2017","unstructured":"Cheng, C., & Huang, L. (2017). Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control. Journal of Manufacturing Systems, 42, 1\u201310.","journal-title":"Journal of Manufacturing Systems"},{"key":"3346_CR10","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1023\/A:1018946810121","volume":"70","author":"RL Daniels","year":"1997","unstructured":"Daniels, R. L., Hoopes, B. J., & Mazzola, J. B. (1997). An analysis of heuristics for the parallel-machine flexible-resource scheduling problem. Annals of Operations Research, 70, 439\u2013472.","journal-title":"Annals of Operations Research"},{"issue":"7","key":"3346_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02024935","volume":"43","author":"BL Dietrich","year":"1993","unstructured":"Dietrich, B. L., & Escudero, L. F. (1993). On modelling the maximum workload allocation for parallel unrelated machines with setups. Annals of Operations Research, 43(7), 357\u2013377.","journal-title":"Annals of Operations Research"},{"key":"3346_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.asoc.2016.07.025","volume":"48","author":"M Djurasevic","year":"2016","unstructured":"Djurasevic, M., Jakobovic, D., & Knezevic, K. (2016). Adaptive scheduling on unrelated machines with genetic programming. Applied Soft Computing, 48, 419\u2013430.","journal-title":"Applied Soft Computing"},{"issue":"1","key":"3346_CR13","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ejor.2018.07.040","volume":"273","author":"Y Gao","year":"2019","unstructured":"Gao, Y., Yuan, J., Ng, C., & Cheng, T. (2019). A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan. European Journal of Operational Research, 273(1), 74\u201381.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"3346_CR14","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"LA Hall","year":"1997","unstructured":"Hall, L. A., Schulz, A. S., Shmoys, D. B., & Wein, J. (1997). Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, 22(3), 513\u2013544.","journal-title":"Mathematics of Operations Research"},{"key":"3346_CR15","unstructured":"Hoogeveen, H., Schuurman, P., & Woeginger, G. J. (1998). Non-approximability results for scheduling problems with minsum criteria. In International conference on integer programming and combinatorial optimization (pp. 353\u2013366). New York: Springer."},{"issue":"5","key":"3346_CR16","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/j.orl.2018.07.006","volume":"46","author":"S J\u00e4ger","year":"2018","unstructured":"J\u00e4ger, S. (2018). Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates. Operations Research Letters, 46(5), 505\u2013509.","journal-title":"Operations Research Letters"},{"issue":"2","key":"3346_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0377-2217(99)00156-3","volume":"120","author":"G Lancia","year":"2000","unstructured":"Lancia, G. (2000). Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan. European Journal of Operational Research, 120(2), 277\u2013288.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"3346_CR18","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF02085647","volume":"50","author":"Y Lee","year":"1994","unstructured":"Lee, Y., & Sherali, H. D. (1994). Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem. Annals of Operations Research, 50(1), 339\u2013365.","journal-title":"Annals of Operations Research"},{"key":"3346_CR19","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"3346_CR20","doi-asserted-by":"publisher","first-page":"2145","DOI":"10.1016\/j.apm.2008.05.019","volume":"33","author":"K Li","year":"2009","unstructured":"Li, K., & Yang, S. (2009). Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms. Applied Mathematical Modelling, 33(4), 2145\u20132158.","journal-title":"Applied Mathematical Modelling"},{"issue":"1\u20134","key":"3346_CR21","first-page":"269","volume":"67","author":"Y Lin","year":"2013","unstructured":"Lin, Y., & Lin, C. (2013). Dispatching rules for unrelated parallel machine scheduling with release dates. International Journal of Advanced Manufacturing Technology, 67(1\u20134), 269\u2013279.","journal-title":"International Journal of Advanced Manufacturing Technology"},{"issue":"2","key":"3346_CR22","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., & Schrijver, A. (1991). Cones of matrices and set-functions and 0\u20131 optimization. SIAM Journal on Optimization, 1(2), 166\u2013190.","journal-title":"SIAM Journal on Optimization"},{"key":"3346_CR23","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.asoc.2015.12.035","volume":"41","author":"MSS Mir","year":"2016","unstructured":"Mir, M. S. S., & Rezaeian, J. (2016). A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines. Applied Soft Computing, 41, 488\u2013504.","journal-title":"Applied Soft Computing"},{"issue":"1\u20134","key":"3346_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1021569406280","volume":"117","author":"E Mokotoff","year":"2002","unstructured":"Mokotoff, E., & Jimeno, J. (2002). Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem. Annals of Operations Research, 117(1\u20134), 133\u2013150.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"3346_CR25","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1016\/j.cor.2006.07.010","volume":"35","author":"R Nessah","year":"2008","unstructured":"Nessah, R., Yalaoui, F., & Chu, C. (2008). A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Computers & Operations Research, 35(4), 1176\u20131190.","journal-title":"Computers & Operations Research"},{"issue":"4","key":"3346_CR26","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0895480194279057","volume":"10","author":"C Phillips","year":"1997","unstructured":"Phillips, C., Stein, C., & Wein, J. (1997). Task scheduling in networks. SIAM Journal on Discrete Mathematics, 10(4), 573\u2013598.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"3346_CR27","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10479-015-2015-1","volume":"240","author":"F Rendl","year":"2016","unstructured":"Rendl, F. (2016). Semidefinite relaxations for partitioning, assignment and ordering problems. Annals of Operations Research, 240(1), 119\u2013140.","journal-title":"Annals of Operations Research"},{"issue":"1","key":"3346_CR28","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10479-012-1164-8","volume":"201","author":"FJ Rodriguez","year":"2012","unstructured":"Rodriguez, F. J., Blum, C., Garc\u00eda-Mart\u00ednez, C., & Lozano, M. (2012). Grasp with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times. Annals of Operations Research, 201(1), 383\u2013401.","journal-title":"Annals of Operations Research"},{"issue":"7","key":"3346_CR29","doi-asserted-by":"publisher","first-page":"1829","DOI":"10.1016\/j.cor.2013.01.018","volume":"40","author":"FJ Rodriguez","year":"2013","unstructured":"Rodriguez, F. J., Lozano, M., Blum, C., & Garc\u00edA-Mart\u00edNez, C. (2013). An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research, 40(7), 1829\u20131841.","journal-title":"Computers & Operations Research"},{"issue":"4","key":"3346_CR30","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"AS Schulz","year":"2002","unstructured":"Schulz, A. S., & Skutella, M. (2002). Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics, 15(4), 450\u2013469.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"3346_CR31","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"HD Sherali","year":"1994","unstructured":"Sherali, H. D., & Adams, W. P. (1994). A hierarchy of relaxations and convex hull characterizations for mixed-integer zeroone programming problems. Discrete Applied Mathematics, 52(1), 83\u2013106.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"3346_CR32","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s10479-014-1538-1","volume":"222","author":"M Siepak","year":"2014","unstructured":"Siepak, M., & J\u00f3zefczyk, J. (2014). Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion. Annals of Operations Research, 222(1), 517\u2013533.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"3346_CR33","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/j.orl.2018.05.007","volume":"46","author":"R Sitters","year":"2018","unstructured":"Sitters, R., & Yang, L. (2018). A ($$2+\\epsilon $$)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. Operations Research Letters, 46(4), 438\u2013442.","journal-title":"Operations Research Letters"},{"issue":"2","key":"3346_CR34","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M Skutella","year":"2001","unstructured":"Skutella, M. (2001). Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM, 48(2), 206\u2013242.","journal-title":"Journal of the ACM"},{"issue":"5","key":"3346_CR35","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1016\/j.orl.2016.07.016","volume":"44","author":"M Skutella","year":"2016","unstructured":"Skutella, M. (2016). A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. Operations Research Letters, 44(5), 676\u2013679.","journal-title":"Operations Research Letters"},{"issue":"3","key":"3346_CR36","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1287\/moor.2015.0757","volume":"41","author":"M Skutella","year":"2016","unstructured":"Skutella, M., Sviridenko, M., & Uetz, M. (2016). Unrelated machine scheduling with stochastic processing times. Mathematics of Operations Research, 41(3), 851\u2013864.","journal-title":"Mathematics of Operations Research"},{"issue":"1\u20132","key":"3346_CR37","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3(1\u20132), 59\u201366.","journal-title":"Naval Research Logistics"},{"issue":"7","key":"3346_CR38","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1080\/00207720903308389","volume":"42","author":"L Tang","year":"2011","unstructured":"Tang, L., & Zhang, Y. (2011). A new lagrangian relaxation algorithm for scheduling dissimilar parallel machines with release dates. International Journal of Systems Science, 42(7), 1133\u20131141.","journal-title":"International Journal of Systems Science"},{"issue":"4","key":"3346_CR39","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1016\/j.cie.2010.02.012","volume":"58","author":"Y Unlu","year":"2010","unstructured":"Unlu, Y., & Mason, S. J. (2010). Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering, 58(4), 785\u2013800.","journal-title":"Computers & Industrial Engineering"},{"issue":"6","key":"3346_CR40","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1287\/opre.47.6.862","volume":"47","author":"JM van Den Akker","year":"1999","unstructured":"van Den Akker, J. M., Hoogeveen, J. A., & van de Velde, S. L. (1999). Parallel machine scheduling by column generation. Operations Research, 47(6), 862\u2013872.","journal-title":"Operations Research"},{"issue":"2","key":"3346_CR41","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1287\/ijoc.14.2.175.119","volume":"14","author":"T Vredeveld","year":"2002","unstructured":"Vredeveld, T., & Hurkens, C. (2002). Experimental comparison of approximation algorithms for scheduling unrelated parallel machines. INFORMS Journal on Computing, 14(2), 175\u2013189.","journal-title":"INFORMS Journal on Computing"},{"issue":"1","key":"3346_CR42","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.ijpe.2004.11.002","volume":"100","author":"F Yalaoui","year":"2006","unstructured":"Yalaoui, F., & Chu, C. (2006). New exact method to solve the $$pm|r_j|\\sum c_j$$ schedule problem. International Journal of Production Economics, 100(1), 168\u2013179.","journal-title":"International Journal of Production Economics"},{"issue":"2","key":"3346_CR43","first-page":"771","volume":"12","author":"X Zhang","year":"2016","unstructured":"Zhang, X., Xu, D., Du, D., & Miao, C. (2016). Approximate algorithms for unrelated machine scheduling to minimize makespan. Management, 12(2), 771\u2013779.","journal-title":"Management"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03346-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-019-03346-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-019-03346-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T23:28:43Z","timestamp":1595633323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-019-03346-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["3346"],"URL":"https:\/\/doi.org\/10.1007\/s10479-019-03346-4","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"26 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}