{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T13:09:02Z","timestamp":1770988142758,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T00:00:00Z","timestamp":1633046400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T00:00:00Z","timestamp":1633046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006692","name":"Universit\u00e0 degli Studi di Torino","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006692","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper deals with the <jats:inline-formula><jats:alternatives><jats:tex-math>$$1|{p-\\text {batch}, s_j\\le b}|\\sum C_j$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mtext>batch<\/mml:mtext>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:msub>\n                        <mml:mi>s<\/mml:mi>\n                        <mml:mi>j<\/mml:mi>\n                      <\/mml:msub>\n                      <mml:mo>\u2264<\/mml:mo>\n                      <mml:mi>b<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>\u2211<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> scheduling problem, where jobs are scheduled in batches on a single machine in order to minimize the total completion time. A <jats:italic>size<\/jats:italic> is given for each job, such that the total size of each batch cannot exceed a fixed capacity <jats:italic>b<\/jats:italic>. A graph-based model is proposed for computing a very effective lower bound based on linear programming; the model, with an exponential number of variables, is solved by column generation and embedded into both a heuristic <jats:italic>price and branch<\/jats:italic> algorithm and an exact branch and price algorithm. The same model is able to handle parallel-machine problems like <jats:inline-formula><jats:alternatives><jats:tex-math>$$Pm|{p-\\text {batch}, s_j\\le b}|\\sum C_j$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>P<\/mml:mi>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mtext>batch<\/mml:mtext>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:msub>\n                        <mml:mi>s<\/mml:mi>\n                        <mml:mi>j<\/mml:mi>\n                      <\/mml:msub>\n                      <mml:mo>\u2264<\/mml:mo>\n                      <mml:mi>b<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>\u2211<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> very efficiently. Computational results show that the new lower bound strongly dominates the bounds currently available in the literature, and the proposed heuristic algorithm is able to achieve high-quality solutions on large problems in a reasonable computation time. For the single-machine case, the exact branch and price algorithm is able to solve all the tested instances with 30 jobs and a good amount of 40-job examples.<\/jats:p>","DOI":"10.1007\/s10951-021-00703-9","type":"journal-article","created":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T20:29:18Z","timestamp":1633120158000},"page":"569-588","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Column generation for minimizing total completion time in a parallel-batching environment"],"prefix":"10.1007","volume":"24","author":[{"given":"A.","family":"Alfieri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8605-0193","authenticated-orcid":false,"given":"A.","family":"Druetto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Grosso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Salassa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,1]]},"reference":[{"key":"703_CR1","unstructured":"Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Prentice-Hall Inc."},{"issue":"10","key":"703_CR2","doi-asserted-by":"publisher","first-page":"2173","DOI":"10.1080\/00207540050028034","volume":"38","author":"M Azizoglu","year":"2000","unstructured":"Azizoglu, M., & Webster, S. (2000). Scheduling a batch processing machine with non-identical job sizes. International Journal of Production Research, 38(10), 2173\u20132184.","journal-title":"International Journal of Production Research"},{"issue":"3","key":"703_CR3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.5267\/j.ijiec.2017.8.003","volume":"9","author":"P Beldar","year":"2018","unstructured":"Beldar, P., & Costa, A. (2018). Single machine batch processing problem with release dates to minimize total completion time. International Journal of Industrial Engineering Computations, 9(3), 331\u2013348.","journal-title":"International Journal of Industrial Engineering Computations"},{"key":"703_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.cor.2015.04.017","volume":"63","author":"M Cabo","year":"2015","unstructured":"Cabo, M., Possani, E., Potts, C. N., & Song, X. (2015). Split-merge: Using exponential neighborhood search for scheduling a batching machine. Computers and Operations Research, 63, 125\u2013135.","journal-title":"Computers and Operations Research"},{"key":"703_CR5","unstructured":"Cachon, G., & Terwiesch, C. (2012). Matching supply with demand: An introduction to operations management. McGraw-Hill Education."},{"issue":"2","key":"703_CR6","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1016\/j.ijpe.2006.02.010","volume":"103","author":"P Damodaran","year":"2006","unstructured":"Damodaran, P., Kumar Manjeshwar, P., & Srihari, K. (2006). Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103(2), 882\u2013891.","journal-title":"International Journal of Production Economics"},{"key":"703_CR7","doi-asserted-by":"crossref","unstructured":"Desrosiers, J., & L\u00fcbbecke, M. E. (2011). Branch-price-and-cut algorithms.","DOI":"10.1002\/9780470400531.eorms0118"},{"issue":"7","key":"703_CR8","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1016\/S0305-0548(00)00078-2","volume":"29","author":"L Dupont","year":"2002","unstructured":"Dupont, L., & Dhaenens-Flipo, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: An exact procedure. Computers and Operations Research, 29(7), 807\u2013819.","journal-title":"Computers and Operations Research"},{"issue":"2","key":"703_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.2307\/3009018","volume":"27","author":"BA Foster","year":"1976","unstructured":"Foster, B. A., & Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Operational Research Quarterly (1970\u20131977), 27(2), 367\u2013384.","journal-title":"Operational Research Quarterly (1970\u20131977)"},{"key":"703_CR10","doi-asserted-by":"crossref","unstructured":"Graham, R., Lawler, E., Lenstra, J., & Rinnooy Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. Hammer, E. Johnson, & B. Korte (Eds.), Discrete optimization II, volume 5 of annals of discrete mathematics (pp. 287\u2013326). Elsevier.","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"703_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.cie.2018.08.009","volume":"125","author":"Z Jia","year":"2018","unstructured":"Jia, Z., Zhang, H., Long, W., Leung, J. Y., Li, K., & Li, W. (2018). A meta-heuristic for minimizing total weighted flow time on parallel batch machines. Computers and Industrial Engineering, 125, 298\u2013308.","journal-title":"Computers and Industrial Engineering"},{"issue":"3","key":"703_CR12","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/S0925-5273(98)00067-X","volume":"55","author":"F Jolai Ghazvini","year":"1998","unstructured":"Jolai Ghazvini, F., & Dupont, L. (1998). Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 55(3), 273\u2013280.","journal-title":"International Journal of Production Economics"},{"key":"703_CR13","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"703_CR14","doi-asserted-by":"crossref","unstructured":"Kosch, S., & Beck, J. C. (2014). A new mip model for parallel-batch scheduling with non-identical job sizes. In H. Simonis (Ed.), Integration of AI and OR techniques in constraint programming (pp. 55\u201370). Springer International Publishing.","DOI":"10.1007\/978-3-319-07046-9_5"},{"issue":"3","key":"703_CR15","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.ejor.2017.06.021","volume":"263","author":"S Li","year":"2017","unstructured":"Li, S. (2017). Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities. European Journal of Operational Research, 263(3), 815\u2013826.","journal-title":"European Journal of Operational Research"},{"key":"703_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.cor.2015.08.006","volume":"66","author":"J Liu","year":"2016","unstructured":"Liu, J., Lin, Z., Chen, Q., & Mao, N. (2016). Controlling delivery and energy performance of parallel batchprocessors in dynamic mould manufacturing. Computers & Operations Research, 66, 116\u2013129.","journal-title":"Computers & Operations Research"},{"issue":"3","key":"703_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.ejor.2012.04.008","volume":"221","author":"A Malapert","year":"2012","unstructured":"Malapert, A., Gu\u00e9ret, C., & Rousseau, L. (2012). A constraint programming approach for a batch processing problem with non-identical job sizes. European Journal of Operational Research, 221(3), 533\u2013545.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"703_CR18","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.ejor.2020.01.065","volume":"285","author":"I Muter","year":"2020","unstructured":"Muter, I. (2020). Exact algorithms to minimize makespan on single and parallel batch processing machines. European Journal of Operational Research, 285(2), 470\u2013483.","journal-title":"European Journal of Operational Research"},{"key":"703_CR19","doi-asserted-by":"crossref","unstructured":"M\u00f6nch, L., Fowler, J. W., & Mason, S.\u00a0J. (2012). Production planning and control for semiconductor wafer fabrication facilities: Modeling, analysis, and systems, volume\u00a052 of operations research\/computer science interfaces series. Springer Science & Business Media.","DOI":"10.1007\/978-1-4614-4472-5"},{"issue":"2","key":"703_CR20","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/j.ejor.2020.03.044","volume":"286","author":"O Ozturk","year":"2020","unstructured":"Ozturk, O. (2020). A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time. European Journal of Operational Research, 286(2), 432\u2013443.","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"703_CR21","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1080\/00207543.2016.1253889","volume":"55","author":"O Ozturk","year":"2017","unstructured":"Ozturk, O., Begen, M. A., & Zaric, G. S. (2017). A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. International Journal of Production Research, 55(6), 1815\u20131831.","journal-title":"International Journal of Production Research"},{"issue":"20","key":"703_CR22","doi-asserted-by":"publisher","first-page":"6022","DOI":"10.1080\/00207543.2011.641358","volume":"50","author":"O Ozturk","year":"2012","unstructured":"Ozturk, O., Espinouse, M.-L., Mascolo, M. D., & Gouin, A. (2012). Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates. International Journal of Production Research, 50(20), 6022\u20136035.","journal-title":"International Journal of Production Research"},{"issue":"10","key":"703_CR23","doi-asserted-by":"publisher","first-page":"1720","DOI":"10.1016\/j.cor.2009.12.007","volume":"37","author":"N Rafiee Parsa","year":"2010","unstructured":"Rafiee Parsa, N., Karimi, B., & Husseinzadeh Kashan, A. (2010). A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers and Operations Research, 37(10), 1720\u20131730.","journal-title":"Computers and Operations Research"},{"key":"703_CR24","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/j.cie.2016.06.008","volume":"99","author":"N Rafiee Parsa","year":"2016","unstructured":"Rafiee Parsa, N., Karimi, B., & Moattar Husseini, S. M. (2016). Minimizing total flow time on a batch processing machine using a hybrid max\u2013min ant system. Computers and Industrial Engineering, 99, 372\u2013381.","journal-title":"Computers and Industrial Engineering"},{"key":"703_CR25","doi-asserted-by":"crossref","unstructured":"Rafiee\u00a0Parsa, N., Keshavarz, T., Karimi, B., & Moattar\u00a0Husseini, S.\u00a0M. (2019). A hybrid neural network approach to minimize total completion time on a single batch processing machine. International Transactions of Operational Research (in press).","DOI":"10.1111\/itor.12665"},{"issue":"7","key":"703_CR26","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1080\/00207549408957026","volume":"32","author":"R Uzsoy","year":"1994","unstructured":"Uzsoy, R. (1994). Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615\u20131635.","journal-title":"International Journal of Production Research"},{"issue":"14","key":"703_CR27","doi-asserted-by":"publisher","first-page":"4245","DOI":"10.1080\/00207543.2010.518995","volume":"49","author":"H Wang","year":"2011","unstructured":"Wang, H. (2011). Solving single batch-processing machine problems using an iterated heuristic. International Journal of Production Research, 49(14), 4245\u20134261.","journal-title":"International Journal of Production Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00703-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00703-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00703-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T08:17:24Z","timestamp":1637050644000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00703-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,1]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["703"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00703-9","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,1]]},"assertion":[{"value":"10 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}