{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:48:59Z","timestamp":1764402539473},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_28","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"260-272","source":"Crossref","is-referenced-by-count":3,"title":["Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines"],"prefix":"10.1007","author":[{"given":"Sheng","family":"Yu","sequence":"first","affiliation":[]},{"given":"Jude-Thaddeus","family":"Ojiaku","sequence":"additional","affiliation":[]},{"given":"Prudence W. H.","family":"Wong","sequence":"additional","affiliation":[]},{"given":"Yinfeng","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"7","key":"28_CR1","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1057\/palgrave.jors.2600740","volume":"50","author":"B. Alidaee","year":"1999","unstructured":"Alidaee, B., Womer, N.K.: Scheduling with time dependent processing times: Review and extensions. J. of Operational Research Society\u00a050(7), 711\u2013720 (1999)","journal-title":"J. of Operational Research Society"},{"key":"28_CR2","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"3","key":"28_CR3","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1287\/opre.38.3.495","volume":"38","author":"S. Browne","year":"1990","unstructured":"Browne, S., Yechiali, U.: Scheduling deteriorating jobs on a single processor. Operations Research\u00a038(3), 495\u2013498 (1990)","journal-title":"Operations Research"},{"issue":"5","key":"28_CR4","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s11741-007-0503-3","volume":"11","author":"M.B. Cheng","year":"2007","unstructured":"Cheng, M.B., Sun, S.J.: A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs. Journal of Shanghai University\u00a011(5), 451\u2013456 (2007)","journal-title":"Journal of Shanghai University"},{"issue":"2","key":"28_CR5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0020-0190(97)00195-6","volume":"65","author":"T.C.E. Cheng","year":"1998","unstructured":"Cheng, T.C.E., Ding, Q.: The complexity of single machine scheduling with release times. Information Processing Letters\u00a065(2), 75\u201379 (1998)","journal-title":"Information Processing Letters"},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00909-8","volume":"152","author":"T.C.E. Cheng","year":"2004","unstructured":"Cheng, T.C.E., Ding, Q., Lin, B.M.T.: A concise survey of scheduling with time-dependent processing times. European J. of OR\u00a0152(1), 1\u201313 (2004)","journal-title":"European J. of OR"},{"key":"28_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"issue":"1","key":"28_CR8","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1016\/j.ejor.2006.04.021","volume":"180","author":"S. Gawiejnowicz","year":"2007","unstructured":"Gawiejnowicz, S.: Scheduling deteriorating jobs subject to job or machine availability constraints. European J. of OR\u00a0180(1), 472\u2013478 (2007)","journal-title":"European J. of OR"},{"key":"28_CR9","volume-title":"Time-Dependent Scheduling","author":"S. Gawiejnowicz","year":"2008","unstructured":"Gawiejnowicz, S.: Time-Dependent Scheduling. Springer, Berlin (2008)"},{"issue":"9","key":"28_CR10","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal\u00a045(9), 1563\u20131581 (1966)","journal-title":"Bell System Technical Journal"},{"issue":"4","key":"28_CR11","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/0360-8352(88)90041-1","volume":"14","author":"J.N.D. Gupta","year":"1988","unstructured":"Gupta, J.N.D., Gupta, S.K.: Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering\u00a014(4), 387\u2013393 (1988)","journal-title":"Computers and Industrial Engineering"},{"issue":"1-3","key":"28_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.06.006","volume":"362","author":"M. Ji","year":"2006","unstructured":"Ji, M., He, Y., Cheng, T.C.E.: Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science\u00a0362(1-3), 115\u2013126 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"28_CR13","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.ijpe.2006.11.014","volume":"109","author":"L.Y. Kang","year":"2007","unstructured":"Kang, L.Y., Ng, C.T.: A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs. International Journal of Production Economics\u00a0109(1-2), 108\u2013184 (2007)","journal-title":"International Journal of Production Economics"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Kononov, A.: Scheduling problems with linear increasing processing times. In: Zimmermann, U., et al. (eds.) Operations Research Proceedings 1996, Berlin, pp. 208\u2013212 (1997)","DOI":"10.1007\/978-3-642-60744-8_38"},{"issue":"1","key":"28_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0377-2217(90)90089-T","volume":"47","author":"A.S. Kunnathur","year":"1990","unstructured":"Kunnathur, A.S., Gupta, S.K.: Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operation Research\u00a047(1), 56\u201364 (1990)","journal-title":"European Journal of Operation Research"},{"issue":"3-4","key":"28_CR16","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF00121681","volume":"9","author":"C.Y. Lee","year":"1996","unstructured":"Lee, C.Y.: Machine scheduling with an availability constraint. Journal of Global Optimization\u00a09(3-4), 395\u2013416 (1996)","journal-title":"Journal of Global Optimization"},{"key":"28_CR17","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"C.Y. Lee","year":"2004","unstructured":"Lee, C.Y.: Machine scheduling with availability constraints. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp. 22.1\u201322.13. Chapman and Hall, Boca Raton (2004)"},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1018909801944","volume":"70","author":"C.Y. Lee","year":"1997","unstructured":"Lee, C.Y., Lei, L., Pinedo, M.: Current trend in deterministic scheduling. Annals of Operations Research\u00a070, 1\u201342 (1997)","journal-title":"Annals of Operations Research"},{"issue":"3","key":"28_CR19","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/j.cie.2007.08.006","volume":"54","author":"W. Lee","year":"2008","unstructured":"Lee, W., Wu, C., Chung, Y.: Scheduling deteriorating jobs on a single machine with release times. Computers and Industrial Engineering\u00a054(3), 441\u2013452 (2008)","journal-title":"Computers and Industrial Engineering"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1287\/opre.39.6.979","volume":"39","author":"G. Mosheiov","year":"1991","unstructured":"Mosheiov, G.: V-shaped policies for scheduling deteriorating jobs. Operations Research\u00a039, 979\u2013991 (1991)","journal-title":"Operations Research"},{"issue":"6","key":"28_CR21","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1016\/0305-0548(94)90080-9","volume":"21","author":"G. Mosheiov","year":"1994","unstructured":"Mosheiov, G.: Scheduling jobs under simple linear deterioration. Computers and Operations Research\u00a021(6), 653\u2013659 (1994)","journal-title":"Computers and Operations Research"},{"issue":"4","key":"28_CR22","first-page":"205","volume":"36","author":"G. Mosheiov","year":"1998","unstructured":"Mosheiov, G.: Multi-machine scheduling with linear deterioration. INFOR: Information Systems and Operational Research\u00a036(4), 205\u2013214 (1998)","journal-title":"INFOR: Information Systems and Operational Research"},{"issue":"40-42","key":"28_CR23","doi-asserted-by":"publisher","first-page":"3578","DOI":"10.1016\/j.tcs.2010.05.032","volume":"411","author":"C.T. Ng","year":"2010","unstructured":"Ng, C.T., Li, S.S., Cheng, T.C.E., Yuan, J.J.: Preemptive scheduling with simple linear deterioration on a single machine. Theoretical Computer Science\u00a0411(40-42), 3578\u20133586 (2010)","journal-title":"Theoretical Computer Science"},{"key":"28_CR24","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M. Pinedo","year":"2002","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Upper Saddle River (2002)"},{"key":"28_CR25","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"K. Pruhs","year":"2004","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp, 15.1\u201315.42. Chapman and Hall, Boca Raton (2004)"},{"issue":"4","key":"28_CR26","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s11741-007-0406-3","volume":"11","author":"C.R. Ren","year":"2007","unstructured":"Ren, C.R., Kang, L.Y.: An approximation algorithm for parallel machine scheduling with simple linear deterioration. Journal of Shanghai University\u00a011(4), 351\u2013354 (2007)","journal-title":"Journal of Shanghai University"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:22:51Z","timestamp":1620127371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}