{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T06:14:18Z","timestamp":1775888058727,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,17]],"date-time":"2015-04-17T00:00:00Z","timestamp":1429228800000},"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":["J Sched"],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s10951-015-0428-y","type":"journal-article","created":{"date-parts":[[2015,4,16]],"date-time":"2015-04-16T03:22:30Z","timestamp":1429154550000},"page":"309-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Exact algorithms for single-machine scheduling with time windows and precedence constraints"],"prefix":"10.1007","volume":"19","author":[{"given":"Morteza","family":"Davari","sequence":"first","affiliation":[]},{"given":"Erik","family":"Demeulemeester","sequence":"additional","affiliation":[]},{"given":"Roel","family":"Leus","sequence":"additional","affiliation":[]},{"given":"Fabrice","family":"Talla Nobibon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,17]]},"reference":[{"issue":"2","key":"428_CR1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1057\/jors.1988.26","volume":"39","author":"TS Abdul-Razaq","year":"1988","unstructured":"Abdul-Razaq, T. S., & Potts, C. N. (1988). Dynamic programming state-space relaxation for single-machine scheduling. Journal of the Operational Research Society, 39(2), 141\u2013152.","journal-title":"Journal of the Operational Research Society"},{"key":"428_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":"428_CR3","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1023\/A:1013741325877","volume":"32","author":"MS Akturk","year":"2000","unstructured":"Akturk, M. S., & Ozdemir, D. (2000). An exact approach to minimizing total weighted tardiness with release dates. IIE Transactions, 32, 1091\u20131101.","journal-title":"IIE Transactions"},{"issue":"2","key":"428_CR4","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/S0377-2217(00)00319-2","volume":"135","author":"MS Akturk","year":"2001","unstructured":"Akturk, M. S., & Ozdemir, D. (2001). A new dominance rule to minimize total weighted tardiness with unequal release dates. European Journal of Operational Research, 135(2), 394\u2013412.","journal-title":"European Journal of Operational Research"},{"key":"428_CR5","volume-title":"Resource-constrained project scheduling: Models, algorithms, extensions and applications","author":"C Artigues","year":"2007","unstructured":"Artigues, C., Demassey, S., & Neron, E. (2007). Resource-constrained project scheduling: Models, algorithms, extensions and applications. London: ISTE."},{"issue":"6","key":"428_CR6","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1137\/0221065","volume":"21","author":"W Bein","year":"1992","unstructured":"Bein, W., Kamburowski, J., & Stallmann, M. (1992). Optimal reduction of two-terminal directed acyclic graphs. SIAM Journal on Computing, 21(6), 1112\u20131129.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"428_CR7","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0166-218X(92)90255-9","volume":"36","author":"H Belouadah","year":"1992","unstructured":"Belouadah, H., Posner, M. E., & Potts, C. N. (1992). Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 36(3), 213\u2013231.","journal-title":"Discrete Applied Mathematics"},{"issue":"1\u20132","key":"428_CR8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00453-011-9523-4","volume":"63","author":"G Calinescu","year":"2012","unstructured":"Calinescu, G., Fernandes, C., Kaul, H., & Zelikovsky, A. (2012). Maximum series-parallel subgraph. Algorithmica, 63(1\u20132), 137\u2013157.","journal-title":"Algorithmica"},{"key":"428_CR9","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/0377-2217(87)90240-2","volume":"29","author":"N Christofides","year":"1987","unstructured":"Christofides, N., Alvarez-Valdes, R., & Tamarit, J. M. (1987). Project scheduling with resource constraints: A branch and bound approach. European Journal of Operational Research, 29, 262\u2013273.","journal-title":"European Journal of Operational Research"},{"key":"428_CR10","volume-title":"Theory of Scheduling","author":"RW Conway","year":"1967","unstructured":"Conway, R. W., Maxwell, W. C., & Miller, L. W. (1967). Theory of Scheduling. Reading, MA: Addison Wesley."},{"issue":"3","key":"428_CR11","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1287\/opre.1060.0358","volume":"55","author":"D Debels","year":"2007","unstructured":"Debels, D., & Vanhoucke, M. (2007). A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Operations Research, 55(3), 457\u2013469.","journal-title":"Operations Research"},{"key":"428_CR12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1023\/A:1022283403119","volume":"6","author":"E Demeulemeester","year":"2003","unstructured":"Demeulemeester, E., Vanhoucke, M., & Herroelen Rangen, W. (2003). A random network generator for activity-on-the-node networks. Journal of Scheduling, 6, 13\u201334.","journal-title":"Journal of Scheduling"},{"issue":"23","key":"428_CR13","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(23), 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"428_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"ML Fisher","year":"1981","unstructured":"Fisher, M. L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science, 27(1), 1\u201318.","journal-title":"Management Science"},{"key":"428_CR15","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman."},{"issue":"3","key":"428_CR16","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1080\/02331939708844360","volume":"42","author":"V Gordon","year":"1997","unstructured":"Gordon, V., Potapneva, E., & Werner, F. (1997). Single machine scheduling with deadlines, release and due dates. Optimization, 42(3), 219\u2013244.","journal-title":"Optimization"},{"key":"428_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"428_CR18","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0166-218X(83)90019-7","volume":"5","author":"AMA Hariri","year":"1983","unstructured":"Hariri, A. M. A., & Potts, C. N. (1983). An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Applied Mathematics, 5(1), 99\u2013109.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"428_CR19","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., & Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196\u2013210.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"428_CR20","first-page":"173","volume":"70","author":"JA Hoogeveen","year":"1995","unstructured":"Hoogeveen, J. A., & van de Velde, S. L. (1995). Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems. Mathematical Programming, 70, 173\u2013190.","journal-title":"Mathematical Programming"},{"issue":"1","key":"428_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(1), 72\u201382.","journal-title":"European Journal of Operational Research"},{"key":"428_CR22","series-title":"Branch and bound algorithms for total weighted tardiness","volume-title":"Handbook of scheduling: Algorithms, models and performance analysis, chap. 13","author":"A Jouglet","year":"2004","unstructured":"Jouglet, A., Baptiste, P., & Carlier, J. (2004). Handbook of scheduling: Algorithms, models and performance analysis, chap. 13., Branch and bound algorithms for total weighted tardiness Boca Raton, FL: CRC Press."},{"key":"428_CR23","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.cie.2008.06.008","volume":"56","author":"AB Keha","year":"2009","unstructured":"Keha, A. B., Khowala, K., & Fowler, J. W. (2009). Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56, 357\u2013367.","journal-title":"Computers & Industrial Engineering"},{"key":"428_CR24","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.cor.2014.02.008","volume":"48","author":"J Kinable","year":"2014","unstructured":"Kinable, J., Wauters, T., & Vanden Berghe, G. (2014). The concrete delivery problem. Computers & Operations Research, 48, 53\u201368.","journal-title":"Computers & Operations Research"},{"issue":"5","key":"428_CR25","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"EL Lawler","year":"1973","unstructured":"Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5), 544\u2013546.","journal-title":"Management Science"},{"key":"428_CR26","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"EL Lawler","year":"1977","unstructured":"Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331\u2013342.","journal-title":"Annals of Discrete Mathematics"},{"key":"428_CR27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"EL Lawler","year":"1978","unstructured":"Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Algorithmic Aspects of Combinatorics, 2, 75\u201390.","journal-title":"Algorithmic Aspects of Combinatorics"},{"key":"428_CR28","series-title":"Complexity of machine scheduling problems. Annals of discrete mathematics","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume-title":"Studies in integer programming","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Studies in integer programming (Vol. 1, pp. 343\u2013362)., Complexity of machine scheduling problems. Annals of discrete mathematics Amsterdam: Elsevier."},{"issue":"2","key":"428_CR29","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0377-2217(93)90180-U","volume":"64","author":"GB McMahon","year":"1993","unstructured":"McMahon, G. B., & Lim, C. J. (1993). The two-machine flow shop problem with arbitrary precedence relations. European Journal of Operational Research, 64(2), 249\u2013257.","journal-title":"European Journal of Operational Research"},{"key":"428_CR30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02684390","volume":"58","author":"G Nemeth","year":"1997","unstructured":"Nemeth, G., Lovrek, I., & Sinkovic, V. (1997). Scheduling problems in parallel systems for telecommunications. Computing, 58, 199\u2013223.","journal-title":"Computing"},{"issue":"3","key":"428_CR31","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.cor.2011.05.024","volume":"39","author":"R Nessah","year":"2012","unstructured":"Nessah, R., & Kacem, I. (2012). Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates. Computers & Operations Research, 39(3), 471\u2013478.","journal-title":"Computers & Operations Research"},{"issue":"6","key":"428_CR32","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/S0167-6377(03)00048-8","volume":"31","author":"Y Pan","year":"2003","unstructured":"Pan, Y. (2003). An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time. Operations Research Letters, 31(6), 492\u2013496.","journal-title":"Operations Research Letters"},{"issue":"4","key":"428_CR33","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/TASE.2005.853474","volume":"2","author":"Y Pan","year":"2005","unstructured":"Pan, Y., & Shi, L. (2005). Dual constrained single machine sequencing to minimize total weighted completion time. IEEE Transactions on Automation Science and Engineering, 2(4), 344\u2013357.","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"428_CR34","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"ML Pinedo","year":"2008","unstructured":"Pinedo, M. L. (2008). Scheduling: Theory, Algorithms, and Systems. Berlin: Springer."},{"key":"428_CR35","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1287\/opre.33.3.562","volume":"33","author":"ME Posner","year":"1985","unstructured":"Posner, M. E. (1985). Minimizing weighted completion times with deadlines. Operations Research, 33, 562\u2013574.","journal-title":"Operations Research"},{"issue":"10","key":"428_CR36","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1287\/mnsc.31.10.1300","volume":"31","author":"CN Potts","year":"1985","unstructured":"Potts, C. N. (1985). A lagrangean based branch and bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time. Management Science, 31(10), 1300\u20131311.","journal-title":"Management Science"},{"issue":"4","key":"428_CR37","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0377-2217(83)90159-5","volume":"12","author":"CN Potts","year":"1983","unstructured":"Potts, C. N., & Van Wassenhove, L. N. (1983). An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. European Journal of Operational Research, 12(4), 379\u2013387.","journal-title":"European Journal of Operational Research"},{"key":"428_CR38","doi-asserted-by":"crossref","unstructured":"Potts, C. N., & Van Wassenhove, L. N. (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33(2), 363\u2013377.","DOI":"10.1287\/opre.33.2.363"},{"key":"428_CR39","volume-title":"Scheduling and load balancing in parallel and distributed systems","year":"1995","unstructured":"Shirazi, B. A., Kavi, K. M., & Hurson, A. R. (Eds.). (1995). Scheduling and load balancing in parallel and distributed systems. Los Alamitos: IEEE Computer Society Press."},{"key":"428_CR40","doi-asserted-by":"crossref","DOI":"10.1201\/9781420044218","volume-title":"Production planning and industrial scheduling: Examples, case studies and applications","author":"DR Sule","year":"2007","unstructured":"Sule, D. R. (2007). Production planning and industrial scheduling: Examples, case studies and applications. Boca Raton: CRC Press."},{"issue":"1","key":"428_CR41","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.cor.2010.06.003","volume":"38","author":"F Talla Nobibon","year":"2011","unstructured":"Talla Nobibon, F., & Leus, R. (2011). Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment. Computers & Operations Research, 38(1), 367\u2013378.","journal-title":"Computers & Operations Research"},{"key":"428_CR42","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":"428_CR43","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"},{"issue":"2","key":"428_CR44","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.ejor.2013.02.048","volume":"229","author":"S Tanaka","year":"2013","unstructured":"Tanaka, S., & Sato, S. (2013). An exact algorithm for the precedence-constrained single-machine scheduling problem. European Journal of Operational Research, 229(2), 345\u2013352.","journal-title":"European Journal of Operational Research"},{"issue":"9","key":"428_CR45","doi-asserted-by":"crossref","first-page":"2625","DOI":"10.1016\/j.cor.2005.10.006","volume":"34","author":"L Tang","year":"2007","unstructured":"Tang, L., Xuan, H., & Liu, J. (2007). Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling. Computers & Operations Research, 34(9), 2625\u20132636.","journal-title":"Computers & Operations Research"},{"issue":"2","key":"428_CR46","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R., & Lawler, E. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2), 298\u2013313.","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20133","key":"428_CR47","first-page":"413","volume":"69","author":"SL Velde van de","year":"1995","unstructured":"van de Velde, S. L. (1995). Dual decomposition of a single-machine scheduling problem. Mathematical Programming, 69(1\u20133), 413\u2013428.","journal-title":"Mathematical Programming"},{"key":"428_CR48","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s10951-010-0181-1","volume":"13","author":"J Akker van den","year":"2010","unstructured":"van den Akker, J., Diepen, G., & Hoogeveen, J. (2010). Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. Journal of Scheduling, 13, 561\u2013576.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"428_CR49","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/32.48943","volume":"16","author":"J Xu","year":"1990","unstructured":"Xu, J., & Parnas, D. (1990). Scheduling processes with release times, deadlines, precedence and exclusion relations. IEEE Transaction on Software Engineering, 16(3), 360\u2013369.","journal-title":"IEEE Transaction on Software Engineering"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-015-0428-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-015-0428-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-015-0428-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T11:06:40Z","timestamp":1566558400000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-015-0428-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,17]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["428"],"URL":"https:\/\/doi.org\/10.1007\/s10951-015-0428-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,17]]}}}