{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T10:21:22Z","timestamp":1774952482255,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,6,23]],"date-time":"2011-06-23T00:00:00Z","timestamp":1308787200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s10951-011-0242-0","type":"journal-article","created":{"date-parts":[[2011,6,22]],"date-time":"2011-06-22T19:40:44Z","timestamp":1308771644000},"page":"347-361","source":"Crossref","is-referenced-by-count":50,"title":["A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time"],"prefix":"10.1007","volume":"15","author":[{"given":"Shunji","family":"Tanaka","sequence":"first","affiliation":[]},{"given":"Shuji","family":"Fujikuma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,23]]},"reference":[{"key":"242_CR1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1057\/jors.1988.26","volume":"39","author":"T. S. Abdul-Razaq","year":"1988","unstructured":"Abdul-Razaq, T. S., & Potts, C. N. (1988). Dynamic programming state-space relaxation for single-machine scheduling. The Journal of the Operational Research Society, 39, 141\u2013152.","journal-title":"The Journal of the Operational Research Society"},{"key":"242_CR2","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1023\/A:1013741325877","volume":"32","author":"M. S. 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"},{"key":"242_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-1479-4","volume-title":"Constraint-based scheduling: Applying constraint programming to scheduling problems","author":"P. Baptiste","year":"2001","unstructured":"Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-based scheduling: Applying constraint programming to scheduling problems. Dordrecht: Kluwer Academic."},{"key":"242_CR4","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, 213\u2013231.","journal-title":"Discrete Applied Mathematics"},{"key":"242_CR5","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1002\/nav.3800290114","volume":"29","author":"L. Bianco","year":"1982","unstructured":"Bianco, L., & Ricciardelli, S. (1982). Scheduling of a single machine to minimize total weighted completion time subject to release dates. Naval Research Logistics Quarterly, 29, 151\u2013167.","journal-title":"Naval Research Logistics Quarterly"},{"key":"242_CR6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02085636","volume":"50","author":"P. Brucker","year":"1994","unstructured":"Brucker, P., Jurisch, B., & Krarner, A. (1994). The job-shop problem and immediate selection. Annals of Operation Research, 50, 73\u2013114.","journal-title":"Annals of Operation Research"},{"key":"242_CR7","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s10951-007-0028-6","volume":"10","author":"K. B\u00fclb\u00fcl","year":"2007","unstructured":"B\u00fclb\u00fcl, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness\/tardiness scheduling. Journal of Scheduling, 10, 271\u2013292.","journal-title":"Journal of Scheduling"},{"key":"242_CR8","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1287\/mnsc.35.2.164","volume":"35","author":"J. Carlier","year":"1989","unstructured":"Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35, 164\u2013176.","journal-title":"Management Science"},{"key":"242_CR9","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/BF03543071","volume":"26","author":"J. Carlier","year":"1990","unstructured":"Carlier, J., & Pinson, E. (1990). A practical use of Jackson\u2019s preemptive scheduling for solving the job-shop problem. Annals of Operation Research, 26, 268\u2013287.","journal-title":"Annals of Operation Research"},{"key":"242_CR10","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/0377-2217(94)90379-4","volume":"78","author":"J. Carlier","year":"1994","unstructured":"Carlier, J., & Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78, 146\u2013161.","journal-title":"European Journal of Operational Research"},{"key":"242_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0898-1221(99)00130-3","volume":"37","author":"P. C. Chang","year":"1999","unstructured":"Chang, P. C. (1999). A branch and bound approach for single machine scheduling with earliness and tardiness penalties. Computers & Mathematics With Applications, 37, 133\u2013144.","journal-title":"Computers & Mathematics With Applications"},{"key":"242_CR12","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230110207","volume":"11","author":"N. Christofides","year":"1981","unstructured":"Christofides, N., Mingozzi, A., & Toth, P. (1981). State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11, 145\u2013164.","journal-title":"Networks"},{"key":"242_CR13","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1287\/ijoc.14.1.52.7712","volume":"14","author":"R. K. Congram","year":"2002","unstructured":"Congram, R. K., Potts, C. N., & van\u00a0de Velde, S. L. (2002). An iterated dynasearch algorithm for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing, 14, 52\u201367.","journal-title":"INFORMS Journal on Computing"},{"key":"242_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1002\/1520-6750(199302)40:1<85::AID-NAV3220400106>3.0.CO;2-C","volume":"40","author":"J. S. Davis","year":"1993","unstructured":"Davis, J. S., & Kanet, J. J. (1993). Single-machine scheduling with early and tardy completion costs. Naval Research Logistics, 40, 85\u2013101.","journal-title":"Naval Research Logistics"},{"key":"242_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ejor.2009.02.005","volume":"201","author":"B. Detienne","year":"2010","unstructured":"Detienne, B., Pinson, \u00c9., & Rivreau, D. (2010). Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates. European Journal of Operational Research, 201, 45\u201354.","journal-title":"European Journal of Operational Research"},{"key":"242_CR16","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M. E. Dyer","year":"1990","unstructured":"Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single-machine sequencing problem with release dates as a mixed integer problem. Discrete Applied Mathematics, 26, 255\u2013270.","journal-title":"Discrete Applied Mathematics"},{"key":"242_CR17","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1287\/inte.15.2.10","volume":"15","author":"M. L. Fisher","year":"1985","unstructured":"Fisher, M. L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces, 15, 10\u201321.","journal-title":"Interfaces"},{"key":"242_CR18","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0305-0548(95)00008-A","volume":"23","author":"T. D. Fry","year":"1996","unstructured":"Fry, T. D., Armstrong, R. D., Darby-Dowman, K., & Philipoom, P. R. (1996). A branch and bound procedure to minimize mean absolute lateness on a single processor. Computers & Operations Research, 23, 171\u2013182.","journal-title":"Computers & Operations Research"},{"key":"242_CR19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1023\/A:1018972726534","volume":"69","author":"S. G\u00e9linas","year":"1997","unstructured":"G\u00e9linas, S., & Soumis, F. (1997). A dynamic programming algorithm for single machine scheduling with ready times. Annals of Operation Research, 69, 135\u2013156.","journal-title":"Annals of Operation Research"},{"key":"242_CR20","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. 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"},{"key":"242_CR21","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0167-6377(03)00064-6","volume":"32","author":"A. Grosso","year":"2004","unstructured":"Grosso, A., Della Croce, F., & Tadei, R. (2004). An enhanced dynasearch neighborhood for the single machine total weighted tardiness scheduling problem. Operations Research Letters, 32, 68\u201372.","journal-title":"Operations Research Letters"},{"key":"242_CR22","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0166-218X(83)90019-7","volume":"5","author":"A. M. A. 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, 99\u2013109.","journal-title":"Discrete Applied Mathematics"},{"key":"242_CR23","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1287\/ijoc.8.4.402","volume":"8","author":"J. A. Hoogeveen","year":"1996","unstructured":"Hoogeveen, J. A., & van\u00a0de Velde, S. L. (1996). A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. INFORMS Journal on Computing, 8, 402\u2013412.","journal-title":"INFORMS Journal on Computing"},{"key":"242_CR24","unstructured":"Ibaraki, T. (1987). Enumerative approaches to combinatorial optimization. Annals of Operations Research, 10 and 11."},{"key":"242_CR25","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":"242_CR26","volume-title":"Handbook of scheduling, algorithms, models, and performance analysis","author":"A. Jouglet","year":"2004","unstructured":"Jouglet, A., Baptiste, P., & Carlier, J. (2004). Branch-and-bound algorithms for total weighted tardiness. In J. Y.-T. Leung (Ed.), Handbook of scheduling, algorithms, models, and performance analysis. Boca Raton: CRC Press (Chap. 13)."},{"key":"242_CR27","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1002\/1520-6750(199412)41:7<913::AID-NAV3220410705>3.0.CO;2-A","volume":"41","author":"Y.-D. Kim","year":"1994","unstructured":"Kim, Y.-D., & Yano, C. A. (1994). Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates. Naval Research Logistics, 41, 913\u2013933.","journal-title":"Naval Research Logistics"},{"key":"242_CR28","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, 344\u2013358.","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"242_CR29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TASE.2007.895005","volume":"5","author":"Y. Pan","year":"2008","unstructured":"Pan, Y., & Shi, L. (2008). New hybrid optimization algorithms for machine scheduling problems. IEEE Transactions on Automation Science and Engineering, 5, 337\u2013348.","journal-title":"IEEE Transactions on Automation Science and Engineering"},{"key":"242_CR30","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/S0377-2217(02)00438-1","volume":"148","author":"L. P\u00e9ridy","year":"2003","unstructured":"P\u00e9ridy, L., Pinson, \u00c9., & Rivreau, D. (2003). Using short-term memory to minimize the weighted number of late jobs on a single machine. European Journal of Operational Research, 148, 591\u2013603.","journal-title":"European Journal of Operational Research"},{"key":"242_CR31","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/opre.33.2.363","volume":"33","author":"C. N. 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":"242_CR32","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/mnsc.16.1.93","volume":"16","author":"A. A. B. Pritsker","year":"1969","unstructured":"Pritsker, A. A. B., Watters, L. J., & Wolfe, P. M. (1969). Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 16, 93\u2013108.","journal-title":"Management Science"},{"key":"242_CR33","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/ijoc.1050.0158","volume":"19","author":"H. D. Sherali","year":"2007","unstructured":"Sherali, H. D., & Lim, C. (2007). Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability. INFORMS Journal on Computing, 19, 3\u201313.","journal-title":"INFORMS Journal on Computing"},{"key":"242_CR34","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF01447654","volume":"20","author":"H. D. Sherali","year":"1989","unstructured":"Sherali, H. D., & Ulular, O. (1989). A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems. Applied Mathematics & Optimization, 20, 193\u2013221.","journal-title":"Applied Mathematics & Optimization"},{"key":"242_CR35","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.ejor.2004.01.025","volume":"165","author":"F. Sourd","year":"2005","unstructured":"Sourd, F. (2005). Optimal timing of a sequence of tasks with general completion cost. European Journal of Operational Research, 165, 82\u201396.","journal-title":"European Journal of Operational Research"},{"key":"242_CR36","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/j.orl.2005.06.005","volume":"34","author":"F. Sourd","year":"2006","unstructured":"Sourd, F. (2006). Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints. Operations Research Letters, 34, 591\u2013598.","journal-title":"Operations Research Letters"},{"key":"242_CR37","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1287\/ijoc.1080.0287","volume":"21","author":"F. Sourd","year":"2009","unstructured":"Sourd, F. (2009). New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS Journal on Computing, 21, 167\u2013175.","journal-title":"INFORMS Journal on Computing"},{"key":"242_CR38","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1023\/A:1026224610295","volume":"6","author":"F. Sourd","year":"2003","unstructured":"Sourd, F., & Kedad-Sidhoum, S. (2003). The one-machine problem with earliness and tardiness penalties. Journal of Scheduling, 6, 533\u2013549.","journal-title":"Journal of Scheduling"},{"key":"242_CR39","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10951-007-0048-2","volume":"11","author":"F. Sourd","year":"2008","unstructured":"Sourd, F., & Kedad-Sidhoum, S. (2008). A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem. Journal of Scheduling, 11, 49\u201358.","journal-title":"Journal of Scheduling"},{"key":"242_CR40","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01586059","volume":"54","author":"J. P. 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":"242_CR41","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":"242_CR42","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/s101070050071","volume":"85","author":"J. M. Akker van\u00a0der","year":"1999","unstructured":"van\u00a0der Akker, J. M., van Hoesel, C. P. M., & Savelsbergh, M. W. P. (1999). A polyhedral approach to single-machine scheduling problems. Mathematical Programming, 85, 541\u2013572.","journal-title":"Mathematical Programming"},{"key":"242_CR43","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/ijoc.12.2.111.11896","volume":"12","author":"J. M. Akker van\u00a0den","year":"2000","unstructured":"van\u00a0den 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":"242_CR44","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0377-2217(91)90078-A","volume":"52","author":"C. A. Yano","year":"1991","unstructured":"Yano, C. A., & Kim, Y.-D. (1991). Algorithms for a class of single-machine weighted tardiness and earliness problems. European Journal of Operational Research, 52, 167\u2013178.","journal-title":"European Journal of Operational Research"},{"key":"242_CR45","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1109\/TASE.2007.895219","volume":"5","author":"H. Yau","year":"2008","unstructured":"Yau, H., Pan, Y., & Shi, L. (2008). New solution approaches to the general single machine earliness-tardiness problem. IEEE Transactions on Automation Science and Engineering, 5, 349\u2013360.","journal-title":"IEEE Transactions on Automation Science and Engineering"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0242-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-011-0242-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0242-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T14:33:10Z","timestamp":1592663590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-011-0242-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,23]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["242"],"URL":"https:\/\/doi.org\/10.1007\/s10951-011-0242-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,23]]}}}