{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T05:25:31Z","timestamp":1747632331880,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T00:00:00Z","timestamp":1670457600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T00:00:00Z","timestamp":1670457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012550","name":"Nemzeti Kutat\u00e1si, Fejleszt\u00e9si \u00e9s Innovaci\u00f3s Alap","doi-asserted-by":"publisher","award":["SNN 129178","TKP2021-NKTA-01"],"award-info":[{"award-number":["SNN 129178","TKP2021-NKTA-01"]}],"id":[{"id":"10.13039\/501100012550","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we consider a combination of the joint replenishment problem (JRP) and single-machine scheduling with release dates. There is a single machine and one or more item types. Each job has a release date, a positive processing time, and it requires a subset of items. A job can be started at time <jats:italic>t<\/jats:italic> only if all the required item types were replenished between the release date of the job and time point <jats:italic>t<\/jats:italic>. The ordering of item types for distinct jobs can be combined. The objective is to minimize the total ordering cost plus a scheduling criterion, such as total weighted completion time or maximum flow time, where the cost of ordering a subset of items simultaneously is the sum of a joint ordering cost, and an additional item ordering cost for each item type in the subset. We provide several complexity results for the offline problem, and competitive analysis for online variants with min\u2013sum and min\u2013max criteria, respectively.<\/jats:p>","DOI":"10.1007\/s10951-022-00768-0","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T22:23:43Z","timestamp":1670538223000},"page":"77-94","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Joint replenishment meets scheduling"],"prefix":"10.1007","volume":"26","author":[{"given":"P\u00e9ter","family":"Gy\u00f6rgyi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2759-1264","authenticated-orcid":false,"given":"Tam\u00e1s","family":"Kis","sequence":"additional","affiliation":[]},{"given":"T\u00edmea","family":"Tam\u00e1si","sequence":"additional","affiliation":[]},{"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"key":"768_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., & Sviridenko, M. (1999). Approximation schemes for minimizing average weighted completion time with release dates. In 40th annual symposium on foundations of computer science (Cat. No. 99CB37039) (pp. 32\u201343). IEEE","DOI":"10.1109\/SFFCS.1999.814574"},{"issue":"3","key":"768_CR2","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/moor.1040.0092","volume":"29","author":"EJ Anderson","year":"2004","unstructured":"Anderson, E. J., & Potts, C. N. (2004). Online scheduling of a single machine to minimize total weighted completion time. Mathematics of Operations Research, 29(3), 686\u2013697.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"768_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0167-6377(89)90001-1","volume":"8","author":"E Arkin","year":"1989","unstructured":"Arkin, E., Joneja, D., & Roundy, R. (1989). Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters, 8(2), 61\u201366.","journal-title":"Operations Research Letters"},{"issue":"6","key":"768_CR4","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1016\/j.orl.2013.10.002","volume":"41","author":"I Averbakh","year":"2013","unstructured":"Averbakh, I., & Baysan, M. (2013). Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem. Operations Research Letters, 41(6), 710\u2013714.","journal-title":"Operations Research Letters"},{"issue":"1","key":"768_CR5","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1016\/j.ejor.2006.06.004","volume":"181","author":"I Averbakh","year":"2007","unstructured":"Averbakh, I., & Xue, Z. (2007). On-line supply chain scheduling problems with preemption. European Journal of Operational Research, 181(1), 500\u2013504.","journal-title":"European Journal of Operational Research"},{"key":"768_CR6","doi-asserted-by":"crossref","unstructured":"Azar, Y., Epstein, A., Je\u017c, L., & Vardi, A. (2016). Make-to-order integrated scheduling and distribution. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms (pp. 140\u2013154). SIAM.","DOI":"10.1137\/1.9781611974331.ch11"},{"issue":"4","key":"768_CR7","doi-asserted-by":"publisher","first-page":"39-es","DOI":"10.1145\/1290672.1290676","volume":"3","author":"N Bansal","year":"2007","unstructured":"Bansal, N., & Dhamdhere, K. (2007). Minimizing weighted flow time. ACM Transactions on Algorithms (TALG), 3(4), 39-es.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"1\u20133","key":"768_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","volume":"103","author":"P Baptiste","year":"2000","unstructured":"Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1\u20133), 21\u201332.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"768_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644028","volume":"6","author":"L Becchetti","year":"2009","unstructured":"Becchetti, L., Marchetti-Spaccamela, A., Vitaletti, A., Korteweg, P., Skutella, M., & Stougie, L. (2009). Latency-constrained aggregation in sensor networks. ACM Transactions on Algorithms (TALG), 6(1), 1\u201320.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"6","key":"768_CR10","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10951-014-0392-y","volume":"18","author":"M Bienkowski","year":"2015","unstructured":"Bienkowski, M., Byrka, J., Chrobak, M., Dobbs, N., Nowicki, T., Sviridenko, M., \u015awirszcz, G., & Young, N. E. (2015). Approximation algorithms for the joint replenishment problem with deadlines. Journal of Scheduling, 18(6), 545\u2013560.","journal-title":"Journal of Scheduling"},{"key":"768_CR11","doi-asserted-by":"crossref","unstructured":"Bienkowski, M., Byrka, J., Chrobak, M., Je\u017c, \u0141., Nogneng, D., & Sgall, J. (2014). Better approximation bounds for the joint replenishment problem. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms (pp. 42\u201354). SIAM.","DOI":"10.1137\/1.9781611973402.4"},{"key":"768_CR12","doi-asserted-by":"crossref","unstructured":"Bosman, T., & Olver, N. (2020). Improved approximation algorithms for inventory problems. In International conference on integer programming and combinatorial optimization (pp. 91\u2013103). Springer.","DOI":"10.1007\/978-3-030-45771-6_8"},{"issue":"4","key":"768_CR13","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1287\/opre.2013.1188","volume":"61","author":"N Buchbinder","year":"2013","unstructured":"Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K., & Sviridenko, M. (2013). Online make-to-order joint replenishment model: Primal\u2013dual competitive algorithms. Operations Research, 61(4), 1014\u20131029.","journal-title":"Operations Research"},{"key":"768_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., & Zhu, A. (2001). Algorithms for minimizing weighted flow time. In Proceedings of the thirty-third annual ACM symposium on theory of computing (pp. 84\u201393).","DOI":"10.1145\/380752.380778"},{"issue":"1","key":"768_CR15","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/S0097539797327180","volume":"31","author":"C Chekuri","year":"2001","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., & Stein, C. (2001). Approximation techniques for average completion time scheduling. SIAM Journal on Computing, 31(1), 146\u2013166.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"768_CR16","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/opre.1080.0688","volume":"58","author":"ZL Chen","year":"2010","unstructured":"Chen, Z. L. (2010). Integrated production and outbound distribution scheduling: Review and extensions. Operations Research, 58(1), 130\u2013148.","journal-title":"Operations Research"},{"issue":"1\u20132","key":"768_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-015-0920-3","volume":"158","author":"M Cheung","year":"2016","unstructured":"Cheung, M., Elmachtoub, A. N., Levi, R., & Shmoys, D. B. (2016). The submodular joint replenishment problem. Mathematical Programming, 158(1\u20132), 207\u2013233.","journal-title":"Mathematical Programming"},{"key":"768_CR18","doi-asserted-by":"crossref","unstructured":"Epstein, L., & Van\u00a0Stee, R. (2001). Lower bounds for on-line single-machine scheduling. In International symposium on mathematical foundations of computer science (pp. 338\u2013350). Springer.","DOI":"10.1007\/3-540-44683-4_30"},{"issue":"2","key":"768_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"MX Goemans","year":"2002","unstructured":"Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M., & Wang, Y. (2002). Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics, 15(2), 165\u2013192.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"768_CR20","doi-asserted-by":"publisher","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. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Annals of Discrete Mathematics"},{"key":"768_CR21","doi-asserted-by":"crossref","unstructured":"Hoogeveen, J. A., & Vestjens, A. P. (1996). Optimal online algorithms for single-machine scheduling. In International conference on integer programming and combinatorial optimization (pp. 404\u2013414). Springer.","DOI":"10.1007\/3-540-61310-2_30"},{"issue":"6","key":"768_CR22","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/BF01189993","volume":"11","author":"AR Karlin","year":"1994","unstructured":"Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. (1994). Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6), 542\u2013571.","journal-title":"Algorithmica"},{"issue":"1","key":"768_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988). Competitive snoopy caching. Algorithmica, 3(1), 79\u2013119.","journal-title":"Algorithmica"},{"key":"768_CR24","unstructured":"Karp, R. M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP congress (1) (Vol.\u00a012, pp. 416\u2013429)."},{"issue":"4","key":"768_CR25","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1137\/S0097539796305778","volume":"28","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H., Tautenhahn, T., & Woeginger, G. (1999). Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM Journal on Computing, 28(4), 1155\u20131166.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"768_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2007.03.007","volume":"186","author":"M Khouja","year":"2008","unstructured":"Khouja, M., & Goyal, S. (2008). A review of the joint replenishment problem literature: 1989\u20132005. European Journal of Operational Research, 186(1), 1\u201316.","journal-title":"European Journal of Operational Research"},{"key":"768_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"768_CR28","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1287\/mnsc.1070.0781","volume":"54","author":"R Levi","year":"2008","unstructured":"Levi, R., Roundy, R., Shmoys, D., & Sviridenko, M. (2008). A constant approximation algorithm for the one-warehouse multiretailer problem. Management Science, 54(4), 763\u2013776.","journal-title":"Management Science"},{"issue":"2","key":"768_CR29","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1287\/moor.1050.0178","volume":"31","author":"R Levi","year":"2006","unstructured":"Levi, R., Roundy, R. O., & Shmoys, D. B. (2006). Primal\u2013dual algorithms for deterministic inventory problems. Mathematics of Operations Research, 31(2), 267\u2013284.","journal-title":"Mathematics of Operations Research"},{"key":"768_CR30","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/11830924_19","volume-title":"Approximation, randomization, and combinatorial optimization. Algorithms and techniques","author":"R Levi","year":"2006","unstructured":"Levi, R., & Sviridenko, M. (2006). Improved approximation algorithm for the one-warehouse multi-retailer problem. In J. D\u00edaz, K. Jansen, J. D. P. Rolim, & U. Zwick (Eds.), Approximation, randomization, and combinatorial optimization. Algorithms and techniques (pp. 188\u2013199). Springer."},{"key":"768_CR31","doi-asserted-by":"crossref","unstructured":"Nonner, T., & Souza, A. (2009). A 5\/3-approximation algorithm for joint replenishment with deadlines. In International conference on combinatorial optimization and applications (pp. 24\u201335). Springer.","DOI":"10.1007\/978-3-642-02026-1_3"},{"issue":"6","key":"768_CR32","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1287\/opre.28.6.1436","volume":"28","author":"CN Potts","year":"1980","unstructured":"Potts, C. N. (1980). Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research, 28(6), 1436\u20131441.","journal-title":"Operations Research"},{"key":"768_CR33","volume-title":"Inventory control: Theory and practice","author":"MK Starr","year":"1962","unstructured":"Starr, M. K., & Miller, D. W. (1962). Inventory control: Theory and practice. Prentice-Hall."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00768-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00768-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00768-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T08:34:09Z","timestamp":1677314049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00768-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,8]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["768"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00768-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2022,12,8]]},"assertion":[{"value":"3 November 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}