{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T21:24:10Z","timestamp":1772832250698,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Heuristics"],"published-print":{"date-parts":[[1998,3]]},"DOI":"10.1023\/a:1009626427432","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T22:47:08Z","timestamp":1040597228000},"page":"287-297","source":"Crossref","is-referenced-by-count":71,"title":["A Fully Polynomial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs"],"prefix":"10.1007","volume":"3","author":[{"given":"Mikhail Y.","family":"Kovalyov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wieslaw","family":"Kubiak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"155928_CR1","doi-asserted-by":"crossref","first-page":"432","DOI":"10.2307\/1427168","volume":"10","author":"S. Browne","year":"1989","unstructured":"Browne, S. and U. Yechiali. (1989). \"Dynamic Priority Rules for Cyclic Type Queues,\" Advances in Applied Probability 10, 432\u2013450.","journal-title":"Advances in Applied Probability"},{"key":"155928_CR2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/opre.38.3.495","volume":"38","author":"S. Browne","year":"1990","unstructured":"Browne, S. and U. Yechiali. (1990). \"Scheduling Deteriorating Jobs on a Single Processor,\" Operations Research 38, 495\u2013498.","journal-title":"Operations Research"},{"key":"155928_CR3","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/BFb0006603","volume":"23","author":"G.V. Gens","year":"1980","unstructured":"Gens, G.V. and E.V. Levner. (1980). \"Fast Approximation Algorithms for Knapsack Type Problems,\" Lecture Notes in Control and Information Science 23, 185\u2013194.","journal-title":"Lecture Notes in Control and Information Science"},{"key":"155928_CR4","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0305-0483(87)90071-5","volume":"15","author":"S.K. Gupta","year":"1988","unstructured":"Gupta, S.K., A.S. Kunnathur, and K. Dandapani. (1988). \"Optimal Repayment Policies for Multiple Loans,\" OMEGA 15, 207\u2013227.","journal-title":"OMEGA"},{"key":"155928_CR5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E. and S. Sahni. (1976). \"Exact and Approximate Algorithms for Scheduling Nonidentical Processors,\" Journal ACM 23, 317\u2013327.","journal-title":"Journal ACM"},{"key":"155928_CR6","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H. and C.E. Kim. (1975). \"Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems,\" Journal ACM 22, 463\u2013468.","journal-title":"Journal ACM"},{"key":"155928_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.8.1.1","volume":"8","author":"D.S. Johnson","year":"1983","unstructured":"Johnson, D.S. and K.A. Niemi. (1983). \"On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees,\" Mathematics of Operations Research 8, 1\u201314.","journal-title":"Mathematics of Operations Research"},{"key":"155928_CR8","first-page":"15","volume-title":"Proc. 6th Southeastern Conference on Combinatorics; Graph Theory; and Computing","author":"R.M. Karp","year":"1975","unstructured":"Karp, R.M. (1975). \"The Fast Approximate Solution of Hard Combinatorial Problems,\" Proc. 6th Southeastern Conference on Combinatorics; Graph Theory; and Computing. Winnipeg: Utilitas Mathematica Publishing, pp. 15\u201331."},{"key":"155928_CR9","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1080\/02331938908843507","volume":"20","author":"M.Y. Kovalyov","year":"1989","unstructured":"Kovalyov, M.Y., Y.M. Shafransky, V.A. Strusevich, V.S. Tanaev, and A.V. Tuzikov. (1989). \"Approximation Scheduling Algorithms: A Survey,\" Optimization 20, 859\u2013878.","journal-title":"Optimization"},{"key":"155928_CR10","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/moor.19.1.86","volume":"19","author":"M.Y. Kovalyov","year":"1994","unstructured":"Kovalyov, M.Y., C.N. Potts, and L.N. van Wassenhove. (1994). \"A Fully Polynomial Approximation Scheme for Scheduling a Single Machine to Minimize Total Weighted Late Work,\" Mathematics of Operations Research 19, 86\u201393.","journal-title":"Mathematics of Operations Research"},{"key":"155928_CR11","unstructured":"Kubiak, W. and S. van de Velde. (1994). \"Scheduling Deteriorating Jobs to Minimize Makespan,\"Working Paper LOPM 94-12, University of Twente."},{"key":"155928_CR12","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0377-2217(90)90089-T","volume":"47","author":"A.S. Kunnathur","year":"1990","unstructured":"Kunnathur, A.S. and S.K. Gupta. (1990). \"Minimizing the Makespan with Late Start Penalties Added to Processing Times in a Single Facility Scheduling Problem,\" European Journal of Operational Research 47, 56\u201364.","journal-title":"European Journal of Operational Research"},{"key":"155928_CR13","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L. (1979). \"Fast Approximation Algorithms for Knapsack Problems,\" Mathematics of Operations Research 4, 339\u2013356.","journal-title":"Mathematics of Operations Research"},{"key":"155928_CR14","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","volume":"8","author":"M.J. Magazine","year":"1981","unstructured":"Magazine, M.J. and O. Oguz. (1981). \"A Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem,\" European Journal of Operations Research 8, 270\u2013273.","journal-title":"European Journal of Operations Research"},{"key":"155928_CR15","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1287\/opre.39.6.979","volume":"39","author":"G. Mosheiov","year":"1991","unstructured":"Mosheiov, G. (1991). \"V-Shaped Policies for Scheduling Deteriorating Jobs,\" Operations Research 39, 979\u2013991.","journal-title":"Operations Research"},{"key":"155928_CR16","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S. (1976). \"Algorithms for Scheduling Independent Tasks,\" Journal ACM 23, 116\u2013127.","journal-title":"Journal ACM"},{"key":"155928_CR17","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1287\/opre.25.6.920","volume":"25","author":"S. Sahni","year":"1977","unstructured":"Sahni, S. (1977). \"General Techniques for Combinatorial Approximation,\" Operations Research 25, 920\u2013936.","journal-title":"Operations Research"},{"key":"155928_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"Smith, W.E. (1956). \"Various Optimizers for Single State Production,\" Naval Research Logistics Quarterly 3, 59\u201366.","journal-title":"Naval Research Logistics Quarterly"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009626427432.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009626427432\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009626427432.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T10:49:29Z","timestamp":1747651769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009626427432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,3]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,3]]}},"alternative-id":["155928"],"URL":"https:\/\/doi.org\/10.1023\/a:1009626427432","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,3]]}}}