{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:24:55Z","timestamp":1759667095702},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s10479-014-1776-2","type":"journal-article","created":{"date-parts":[[2014,12,29]],"date-time":"2014-12-29T19:56:00Z","timestamp":1419882960000},"page":"197-213","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Dual relaxations of the time-indexed ILP formulation for min\u2013sum scheduling problems"],"prefix":"10.1007","volume":"249","author":[{"given":"Yunpeng","family":"Pan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Liang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"1776_CR1","doi-asserted-by":"crossref","unstructured":"Abdul-Razaq, T. S., & Potts, C. N. (1988). Dynamic programming state-space relaxation for single machine scheduling. Journal of Operational Research Society, 39, 141\u2013152.","DOI":"10.1057\/jors.1988.26"},{"key":"1776_CR2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0166-218X(90)90103-J","volume":"26","author":"TS Abdul-Razaq","year":"1990","unstructured":"Abdul-Razaq, T. S., Potts, C. N., & van Wassenhove, L. N. (1990). A survey of algorithms for the single machine total weighted tardiness scheduling problem. Discrete Applied Mathematics, 26, 235\u2013253.","journal-title":"Discrete Applied Mathematics"},{"key":"1776_CR3","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1287\/ijoc.1040.0069","volume":"17","author":"P Avella","year":"2005","unstructured":"Avella, P., Boccia, M., & D\u2019Auria, B. (2005). Near-optimal solutions of large-scale single-machine scheduling problems. INFORMS Journal on Computing, 17, 183\u2013191.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1023\/B:ANOR.0000030680.29037.d0","volume":"129","author":"P Babu","year":"2004","unstructured":"Babu, P., Peridy, L., & Pinson, E. (2004). A branch and bound algorithm to minimize total weighted tardiness on a single processor. Annals of Operations Research, 129, 33\u201346.","journal-title":"Annals of Operations Research"},{"key":"1776_CR5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46, 316\u2013329.","journal-title":"Operations Research"},{"key":"1776_CR6","unstructured":"Beasley, J. E. (1990). OR-Library. http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/orlib\/wtinfo.html"},{"key":"1776_CR7","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1073\/pnas.39.9.947","volume":"39","author":"R Bellman","year":"1953","unstructured":"Bellman, R. (1953). Bottleneck problems and dynamic programming. Proceedings of the National Academy of Sciences of the United States of America, 39, 947\u2013951.","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"1776_CR8","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1016\/j.orl.2005.10.001","volume":"34","author":"H Ben Amor","year":"2006","unstructured":"Ben Amor, H., Desrosiers, J., & Soumis, F. (2006). Recovering an optimal LP basis from an optimal dual solution. Operations Research Letters, 34, 569\u2013576.","journal-title":"Operations Research Letters"},{"key":"1776_CR9","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1287\/ijoc.1070.0225","volume":"20","author":"L-P Bigras","year":"2007","unstructured":"Bigras, L.-P., Gamache, M., & Savard, G. (2007). Time-indexed formulations and the total weighted tardiness problem. INFORMS Journal on Computing, 20, 133\u2013142.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR10","first-page":"1","volume-title":"Handbook of scheduling: Algorithms, models, and performance analysis, chap. 11.","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., & Khanna, S. (2004). Approximation algorithms for minimizing average weighted completion time. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis, chap. 11. (pp. 1\u201330). Boca Raton, FL: Chapman & Hall \/ CRC."},{"key":"1776_CR11","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1287\/ijoc.14.1.52.7712","volume":"13","author":"RK Congram","year":"2002","unstructured":"Congram, R. K., Potts, C. N., & van de Velde, S. L. (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 13, 52\u201367.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR12","unstructured":"CPLEX. (2005). CPLEX callable library, version 9.1. CPLEX: A division of ILOG."},{"key":"1776_CR13","volume-title":"Combinatorial auctions","author":"P Cramton","year":"2006","unstructured":"Cramton, P., Shoham, Y., & Steinberg, R. (2006). Combinatorial auctions. Cambridge, MA: MIT Press."},{"key":"1776_CR14","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1287\/ijoc.15.3.284.16077","volume":"15","author":"S Vries de","year":"2003","unstructured":"de Vries, S., & Vohra, R. V. (2003). Combinatorial auctions: A survey. INFORMS Journal on Computing, 15, 284\u2013309.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/b135457","volume-title":"Column generation","author":"G Desaulniers","year":"2005","unstructured":"Desaulniers, G., Desrosiers, J., & Solomon, M. (2005). Column generation. Heidelberg: Springer."},{"key":"1776_CR16","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"ME Dyer","year":"1990","unstructured":"Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26, 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"key":"1776_CR17","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1002\/nav.10103","volume":"51","author":"M Elshafei","year":"2004","unstructured":"Elshafei, M., Sherali, H. D., & Smith, J. C. (2004). Radar pulse interleaving for multi-target tracking. Naval Research Logistics, 51, 72\u201394.","journal-title":"Naval Research Logistics"},{"key":"1776_CR18","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01580393","volume":"11","author":"ML Fisher","year":"1976","unstructured":"Fisher, M. L. (1976). A dual algorithm for the one-machine scheduling problem. Mathematical Programming, 11, 229\u2013251.","journal-title":"Mathematical Programming"},{"key":"1776_CR19","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.1040.0332","volume":"51","author":"O G\u00fcnl\u00fck","year":"2005","unstructured":"G\u00fcnl\u00fck, O., & Lad\u00e1nyi, L. (2005). A branch-and-price algorithm and new test problems for spectrum auctions. Management Science, 51, 391\u2013406.","journal-title":"Management Science"},{"key":"1776_CR20","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"3","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, 3, 513\u2013544.","journal-title":"Mathematics of Operations Research"},{"key":"1776_CR21","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/0377-2217(94)90007-8","volume":"76","author":"T Ibaraki","year":"1994","unstructured":"Ibaraki, T., & Nakamura, Y. (1994). A dynamic programming method for single machine scheduling. European Journal of Operational Research, 76, 72\u201382.","journal-title":"European Journal of Operational Research"},{"key":"1776_CR22","doi-asserted-by":"crossref","unstructured":"K\u00e4stner, D., & Winkel, S. (2001). ILP-based instruction scheduling for IA-64. In Proceedings of the ACM SIGPLAN workshop on languages, compilers and tools for embedded systems (pp. 145\u2013154) Snow Bird, Utah.","DOI":"10.1145\/384197.384217"},{"key":"1776_CR23","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1016\/j.ejor.2006.05.052","volume":"189","author":"S Kedad-Sidhoum","year":"2008","unstructured":"Kedad-Sidhoum, S., Rios Solis, Y. A., & Sourd, F. (2008). Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines with distinct due dates. European Journal of Operational Research, 189, 1305\u20131316.","journal-title":"European Journal of Operational Research"},{"key":"1776_CR24","volume-title":"Optimization Theory for Large Systems","author":"LS Lasdon","year":"1970","unstructured":"Lasdon, L. S. (1970). Optimization Theory for Large Systems. New York: Macmillan."},{"key":"1776_CR25","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53, 1007\u20131023.","journal-title":"Operations Research"},{"key":"1776_CR26","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1287\/mnsc.49.3.330.12737","volume":"49","author":"RH M\u00f6hring","year":"2003","unstructured":"M\u00f6hring, R. H., Schulz, A. S., Stork, M., & Uetz, F. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49, 330\u2013350.","journal-title":"Management Science"},{"key":"1776_CR27","doi-asserted-by":"crossref","unstructured":"Pan, Y. (2013). A combinatorial auctions perspective on min-sum scheduling problems. In Proceedings of the 9th Annual IEEE International Conference on Automation Science and Engineering (pp.564\u2013569) Madison, Wisconsin.","DOI":"10.1109\/CoASE.2013.6653895"},{"key":"1776_CR28","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/s10107-006-0013-4","volume":"110","author":"Y Pan","year":"2007","unstructured":"Pan, Y., & Shi, L. (2007). On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems. Mathematical Programming, 110, 543\u2013559.","journal-title":"Mathematical Programming"},{"key":"1776_CR29","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/opre.33.2.363","volume":"33","author":"CN Potts","year":"1985","unstructured":"Potts, C. N., & van Wassenhove, L. N. (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33, 363\u2013377.","journal-title":"Operations Research"},{"key":"1776_CR30","unstructured":"Queyranne, M., & Schulz, A. S. (1994). Polyhedral approaches to machine scheduling. Preprint 408\/1994, Math. Dept., Tech. Univ. Berlin. Revised June 1997."},{"key":"1776_CR31","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1287\/mnsc.1040.0336","volume":"51","author":"T Sandholm","year":"2005","unstructured":"Sandholm, T., Suri, S., Gilpin, A., & Levine, D. (2005). CABOB: A fast optimal algorithm for winner determination in combinatorial auctions. Management Science, 51, 374\u2013390.","journal-title":"Management Science"},{"key":"1776_CR32","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1287\/ijoc.1030.0034","volume":"16","author":"F Sourd","year":"2004","unstructured":"Sourd, F. (2004). The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions. INFORMS Journal on Computing, 16, 198\u2013208.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR33","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01586059","volume":"54","author":"JP Sousa","year":"1992","unstructured":"Sousa, J. P., & Wolsey, L. A. (1992). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 54, 353\u2013367.","journal-title":"Mathematical Programming"},{"key":"1776_CR34","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10951-011-0242-0","volume":"15","author":"S Tanaka","year":"2012","unstructured":"Tanaka, S., & Fujikuma, S. (2012). A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time. Journal of Scheduling, 15, 347\u2013361.","journal-title":"Journal of Scheduling"},{"key":"1776_CR35","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/s10951-008-0093-5","volume":"12","author":"S Tanaka","year":"2009","unstructured":"Tanaka, S., Fujikuma, S., & Araki, M. (2009). An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling, 12, 575\u2013593.","journal-title":"Journal of Scheduling"},{"key":"1776_CR36","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/ijoc.12.2.111.11896","volume":"12","author":"JM Akker van den","year":"2000","unstructured":"van den Akker, J. M., Hurkens, C. A. J., & Savelsbergh, M. W. P. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12, 111\u2013124.","journal-title":"INFORMS Journal on Computing"},{"key":"1776_CR37","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0167-6377(96)00033-8","volume":"19","author":"F Vanderbeck","year":"1996","unstructured":"Vanderbeck, F., & Wolsey, L. A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19, 151\u2013159.","journal-title":"Operations Research Letters"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-014-1776-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-014-1776-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-014-1776-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-014-1776-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:09:55Z","timestamp":1559153395000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-014-1776-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["1776"],"URL":"https:\/\/doi.org\/10.1007\/s10479-014-1776-2","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]}}}