{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:36Z","timestamp":1740103836814,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T00:00:00Z","timestamp":1582243200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T00:00:00Z","timestamp":1582243200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001835","name":"Maastricht University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001835","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a single-machine lot-sizing problem, where <jats:italic>n<\/jats:italic> types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the machine switches production between products, sequencing costs are incurred. These sequencing costs depend both on the product the machine just produced and on the product the machine is about to produce. The goal is to find a cyclic schedule minimizing total average costs, subject to the condition that all demands are satisfied. We establish the complexity of the problem, and we prove a number of structural properties largely characterizing optimal solutions. Moreover, we present two algorithms approximating the optimal schedules by augmenting the problem input. Due to the high-multiplicity setting, even trivial cases of the corresponding conventional counterparts become highly non-trivial with respect to the output sizes and computational complexity, even without sequencing costs. In particular, the length of an optimal solution can be exponential in the input size of the problem. Nevertheless, our approximation algorithms produce schedules of a polynomial length and with a good quality compared to the optimal schedules of exponential length.\n<\/jats:p>","DOI":"10.1007\/s10951-020-00645-8","type":"journal-article","created":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T14:04:15Z","timestamp":1582293855000},"page":"123-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Cyclic lot-sizing problems with sequencing costs"],"prefix":"10.1007","volume":"24","author":[{"given":"Alexander","family":"Grigoriev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent J.","family":"Kreuzen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8509-7002","authenticated-orcid":false,"given":"Tim","family":"Oosterwijk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"issue":"5","key":"645_CR1","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1287\/opre.51.5.798.16748","volume":"51","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., Gamarnik, D., & Sethuraman, J. (2003). From fluid relaxations to practical algorithms for high-multiplicity job-shop scheduling: The holding cost objective. Operations Research, 51(5), 798\u2013813.","journal-title":"Operations Research"},{"issue":"7","key":"645_CR2","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1287\/mnsc.28.7.798","volume":"28","author":"F Boctor","year":"1982","unstructured":"Boctor, F. (1982). The two-product, single-machine, static demand, infinite horizon lot scheduling problem. Management Science, 28(7), 798\u2013807.","journal-title":"Management Science"},{"issue":"3","key":"645_CR3","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s10878-005-1414-7","volume":"9","author":"N Brauner","year":"2005","unstructured":"Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2005). A framework for the complexity of high-multiplicity scheduling problems. Journal of Combinatorial Optimization, 9(3), 313\u2013323.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"645_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1111\/j.1467-9574.2007.00362.x","volume":"61","author":"N Brauner","year":"2007","unstructured":"Brauner, N., Crama, Y., Grigoriev, A., & van de Klundert, J. (2007). Multiplicity and complexity issues in contemporary production scheduling. Statistica Neerlandica, 61(1), 75\u201391.","journal-title":"Statistica Neerlandica"},{"issue":"5","key":"645_CR5","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1287\/opre.48.5.788.12405","volume":"48","author":"J Clifford","year":"2000","unstructured":"Clifford, J., & Posner, M. (2000). High multiplicity in earliness\u2013tardiness scheduling. Operations Research, 48(5), 788\u2013800.","journal-title":"Operations Research"},{"issue":"3","key":"645_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00011403","volume":"89","author":"J Clifford","year":"2001","unstructured":"Clifford, J., & Posner, M. (2001). Parallel machine scheduling with high multiplicity. Mathematical Programming, 89(3), 359\u2013383.","journal-title":"Mathematical Programming"},{"issue":"5","key":"645_CR7","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s10951-009-0122-z","volume":"12","author":"C Filippi","year":"2009","unstructured":"Filippi, C., & Romanin-Jacur, G. (2009). Exact and approximate algorithms for high-multiplicity parallel machine scheduling. Journal of Scheduling, 12(5), 529\u2013541.","journal-title":"Journal of Scheduling"},{"key":"645_CR8","doi-asserted-by":"crossref","unstructured":"Gabay, M., Grigoriev, A., Kreuzen, V. J. C., & Oosterwijk, T. (2016). High multiplicity scheduling with switching costs for few products. In: M.\u00a0L\u00fcbbecke, A.\u00a0Koster, P.\u00a0Letmathe, R.\u00a0Madlener, B.\u00a0Peis & G.\u00a0Walther (Eds.), Operations research proceedings 2014 (pp. 437\u2013443). Springer International Publishing","DOI":"10.1007\/978-3-319-28697-6_61"},{"issue":"2","key":"645_CR9","first-page":"109","volume":"29","author":"G Gallego","year":"1997","unstructured":"Gallego, G., & Shaw, D. X. (1997). Complexity of the elsp with general cyclic schedules. IIE Transactions, 29(2), 109\u2013113.","journal-title":"IIE Transactions"},{"issue":"2","key":"645_CR10","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1057\/jors.1973.43","volume":"24","author":"S Goyal","year":"1973","unstructured":"Goyal, S. (1973). Scheduling a multi-product single machine system. Journal of the Operational Research Society, 24(2), 261\u2013269.","journal-title":"Journal of the Operational Research Society"},{"issue":"1","key":"645_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF01539882","volume":"18","author":"K Haase","year":"1996","unstructured":"Haase, K. (1996). Capacitated lot-sizing with sequence dependent setup costs. Operations-Research-Spektrum, 18(1), 51\u201359.","journal-title":"Operations-Research-Spektrum"},{"issue":"2","key":"645_CR12","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-5273(99)00119-X","volume":"66","author":"K Haase","year":"2000","unstructured":"Haase, K., & Kimms, A. (2000). Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities. International Journal of Production Economics, 66(2), 159\u2013169.","journal-title":"International Journal of Production Economics"},{"issue":"4","key":"645_CR13","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1287\/opre.39.4.648","volume":"39","author":"D Hochbaum","year":"1991","unstructured":"Hochbaum, D., & Shamir, R. (1991). Strongly polynomial algorithms for the high multiplicity scheduling problem. Operations Research, 39(4), 648\u2013653.","journal-title":"Operations Research"},{"issue":"C","key":"645_CR14","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.ijpe.2014.03.024","volume":"155","author":"M Holmbom","year":"2014","unstructured":"Holmbom, M., & Segerstedt, A. (2014). Economic order quantities in production: From Harris to economic lot scheduling problems. International Journal of Production Economics, 155(C), 82\u201390.","journal-title":"International Journal of Production Economics"},{"issue":"3","key":"645_CR15","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R Karp","year":"1978","unstructured":"Karp, R. (1978). A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23(3), 309\u2013311.","journal-title":"Discrete Mathematics"},{"issue":"11","key":"645_CR16","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1287\/mnsc.14.11.713","volume":"14","author":"J Madigan","year":"1968","unstructured":"Madigan, J. (1968). Scheduling a multi-product single machine system for an infinite planning period. Management Science, 14(11), 713\u2013719.","journal-title":"Management Science"},{"issue":"1\u20133","key":"645_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0925-5273(91)90058-2","volume":"23","author":"M Narro Lopez","year":"1991","unstructured":"Narro Lopez, M., & Kingsman, B. (1991). The economic lot scheduling problem: Theory and practice. International Journal of Production Economics, 23(1\u20133), 147\u2013164.","journal-title":"International Journal of Production Economics"},{"issue":"3","key":"645_CR18","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1287\/opre.14.3.532","volume":"14","author":"M Rothkopf","year":"1966","unstructured":"Rothkopf, M. (1966). The traveling salesman problem: On the reduction of certain large problems to smaller ones. Operations Research, 14(3), 532\u2013533.","journal-title":"Operations Research"},{"key":"645_CR19","unstructured":"Wetsels, N. (2012). Production cycle problem. Master\u2019s thesis, Maastricht University, School of Business and Economics"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00645-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-020-00645-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-020-00645-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,7]],"date-time":"2021-04-07T17:11:10Z","timestamp":1617815470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-020-00645-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,21]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["645"],"URL":"https:\/\/doi.org\/10.1007\/s10951-020-00645-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2020,2,21]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}