{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T01:40:37Z","timestamp":1780105237495,"version":"3.54.0"},"publisher-location":"Singapore","reference-count":30,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819502141","type":"print"},{"value":"9789819502158","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-0215-8_6","type":"book-chapter","created":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T16:25:36Z","timestamp":1753979136000},"page":"68-80","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Online Approximation Algorithms for\u00a0Two-Stage Bins"],"prefix":"10.1007","author":[{"given":"Guangwei","family":"Wu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongyun","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guozhen","family":"Rong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feng","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,1]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2022.04.004","volume":"921","author":"J Chen","year":"2022","unstructured":"Chen, J., Huang, M., Guo, Y.: Scheduling multiple two-stage flowshops with a deadline. Theor. Comput. Sci. 921, 100\u2013111 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2016.04.046","volume":"657","author":"J Dong","year":"2017","unstructured":"Dong, J., et al.: An fptas for the parallel two-stage flowshop problem. Theor. Comput. Sci. 657, 64\u201372 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ejor.2019.08.019","volume":"281","author":"J Dong","year":"2020","unstructured":"Dong, J., Jin, R., Luo, T., Tong, W.: A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops. Eur. J. Oper. Res. 281(1), 16\u201324 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1080\/07408179608966258","volume":"28","author":"D He","year":"1996","unstructured":"He, D., Kusiak, A., Artiba, A.: A scheduling problem in glass manufacturing. IIE Trans. 28, 129\u2013139 (1996)","journal-title":"IIE Trans."},{"key":"6_CR5","unstructured":"Kovalyov, M.: Efficient $$\\epsilon $$-approximation algorithm for minimizing the makespan in a parallel two-stage system, Vesti Academii navuk Belaruskai SSR, Ser. Phiz.-Mat. Navuk 3,119 (1985)"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/j.tcs.2022.04.044","volume":"922","author":"W Tong","year":"2022","unstructured":"Tong, W., Xu, Y., Zhang, H.: A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint. Theor. Comput. Sci. 922, 438\u2013446 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2019.01.017","volume":"776","author":"G Wu","year":"2019","unstructured":"Wu, G., Chen, J., Wang, J.: Scheduling two-stage jobs on multiple flowshops. Theor. Comput. Sci. 776, 117\u2013124 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2018.04.017","volume":"818","author":"G Wu","year":"2020","unstructured":"Wu, G., Chen, J., Wang, J.: On scheduling multiple two-stage flowshops. Theor. Comput. Sci. 818, 74\u201382 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"6_CR9","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/j.ejor.2011.08.007","volume":"216","author":"X Zhang","year":"2012","unstructured":"Zhang, X., van de Velde, S.: Approximation algorithms for the parallel flow shop problem. Eur. J. Oper. Res. 216(3), 544\u2013552 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"13","key":"6_CR10","doi-asserted-by":"publisher","first-page":"1539","DOI":"10.1016\/j.comcom.2010.06.024","volume":"34","author":"Y Zhang","year":"2011","unstructured":"Zhang, Y., Zhou, Y.: Separating computation and storage with storage virtualization. Comput. Commun. 34(13), 1539\u20131548 (2011)","journal-title":"Comput. Commun."},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/1721654.1721672","volume":"53","author":"M Armbrust","year":"2010","unstructured":"Armbrust, M., et al.: A view of cloud computing. Commun. ACM 53(4), 50\u201358 (2010)","journal-title":"Commun. ACM"},{"issue":"2","key":"6_CR12","first-page":"1","volume":"53","author":"P Cong","year":"2020","unstructured":"Cong, P., Xu, G., Wei, T., Li, K.: A survey of profit optimization techniques for cloud providers. ACM Comput. Surv. 53(2), 1\u201335 (2020)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1145\/1496091.1496103","volume":"39","author":"A Greenberg","year":"2009","unstructured":"Greenberg, A., Hamilton, J., Maltz, D.A., Patel, P.: The cost of a cloud: research problems in data center networks. ACM SIGCOMM Comput. Commun. Rev. 39(1), 68\u201373 (2009)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Coffman, E.G., Galambos, G., Martello, S., Vigo, D.: Bin Packing Approximation Algorithms: Combinatorial Analysis, pp. 151\u2013207. Springer, US, Boston, MA (1999)","DOI":"10.1007\/978-1-4757-3023-4_3"},{"key":"6_CR15","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1979)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, USA, p. 2616\u20132625 (2017)","DOI":"10.1137\/1.9781611974782.172"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: Approximating bin packing within o (log opt\u00b7 log log opt) bins. In: Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, pp. 20\u201329 (2013)","DOI":"10.1109\/FOCS.2013.11"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science, pp. 312\u2013320. IEEE (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"6_CR19","unstructured":"Johnson, D.S.: Near-optimal bin packing algorithms (1973)"},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A.J., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"6_CR22","unstructured":"Ullman, J.D.: The performance of a memory allocation algorithm, Technical report 100. Princeton University, Princeton, NJ (1971)"},{"issue":"2","key":"6_CR23","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0602019","volume":"2","author":"BS Baker","year":"1981","unstructured":"Baker, B.S., Coffman, E.G., Jr.: A tight asymptotic bound for next-fit-decreasing bin-packing. SIAM J. Algebraic Discrete Methods 2(2), 147\u2013152 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G.: The tight bound of first fit decreasing bin-packing algorithm is ffd($$i$$) $$\\le $$ 11\/9 opt($$i$$)+ 6\/9. In: Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pp. 1\u201311 (2007)","DOI":"10.1007\/978-3-540-74450-4_1"},{"issue":"4","key":"6_CR25","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02009683","volume":"7","author":"M Yue","year":"1991","unstructured":"Yue, M.: A simple proof of the inequality ffd($$l$$) $$\\le $$ 11\/9 opt($$l$$) + 1, $$\\forall l$$ for the ffd bin-packing algorithm. Acta Math. Appl. Sin. 7(4), 321\u2013331 (1991)","journal-title":"Acta Math. Appl. Sin."},{"issue":"3","key":"6_CR26","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1145\/3828.3833","volume":"32","author":"CC Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A simple on-line bin-packing algorithm. J. ACM 32(3), 562\u2013572 (1985)","journal-title":"J. ACM"},{"key":"6_CR27","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing, in: Proceedings of the 26th Annual European Symposium on Algorithms, Vol. 112, Dagstuhl, Germany, pp. 5:1\u20135:14 (2018)"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Sgall, J., van Stee, R.: The optimal absolute ratio for online bin packing. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, USA, p. 1425\u20131438 (2015)","DOI":"10.1137\/1.9781611973730.94"},{"key":"6_CR29","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1007\/s00453-021-00818-7","volume":"83","author":"J Balogh","year":"2021","unstructured":"Balogh, J., B\u00e9k\u00e9si, J., D\u00f3sa, G., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. Algorithmica 83, 2047\u20132062 (2021)","journal-title":"Algorithmica"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1(1), 61\u201368 (1954)","journal-title":"Nav. Res. Logist. Q."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-0215-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T09:34:16Z","timestamp":1757324056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-0215-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,1]]},"ISBN":["9789819502141","9789819502158"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-0215-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,1]]},"assertion":[{"value":"1 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/cocoon2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}