{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:36:58Z","timestamp":1742963818481,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":28,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819977420"},{"type":"electronic","value":"9789819977437"}],"license":[{"start":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T00:00:00Z","timestamp":1700956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T00:00:00Z","timestamp":1700956800000},"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":[[2024]]},"DOI":"10.1007\/978-981-99-7743-7_8","type":"book-chapter","created":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T09:02:16Z","timestamp":1700902936000},"page":"133-147","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scheduling with\u00a0Hierarchies and\u00a0Overload Cost"],"prefix":"10.1007","author":[{"given":"Yaru","family":"Yang","sequence":"first","affiliation":[]},{"given":"Wuyun","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Honglin","family":"Ding","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,26]]},"reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N Alon","year":"1998","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. Sched. 1(1), 55\u201366 (1998)","journal-title":"J. Sched."},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1137\/S0097539798346135","volume":"31","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Freund, A., Naor, J.: On-line load balancing in a hierarchical server topology. SIAM J. Comput. 31(2), 527\u2013549 (2001)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"8_CR3","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s10951-015-0464-7","volume":"19","author":"X Chen","year":"2016","unstructured":"Chen, X., Sterna, M., Han, X., Blazewicz, J.: Scheduling on parallel identical machines with late work criterion: offline and online cases. Int. J. Sched. 19(6), 729\u2013736 (2016)","journal-title":"Int. J. Sched."},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.dam.2020.05.023","volume":"290","author":"X Chen","year":"2021","unstructured":"Chen, X., Kovalev, S., Liu, Y., Sterna, M., Chalamon, I., Blazewicz, J.: Semi-online scheduling on two identical machines with a common due date to maximize total early work. Discret. Appl. Math. 290, 71\u201378 (2021)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10951-006-5594-5","volume":"9","author":"EG Coffman Jr","year":"2006","unstructured":"Coffman, E.G., Jr., Lueker, G.S.: Approximation algorithms for extensible bin packing. J. Sched. 9(1), 63\u201369 (2006)","journal-title":"J. Sched."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Dai, B., Li, J., Li, W.: Semi-online hierarchical scheduling for bag-of-tasks on two machines. In: 2nd International Conference on Computer Science and Artificial Intelligence Proceedings, pp. 609\u2013614. Association for Computing Machinery, New York, United States (2018)","DOI":"10.1145\/3297156.3297222"},{"issue":"5","key":"8_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(97)00216-0","volume":"65","author":"P Dell\u2019Olmo","year":"1998","unstructured":"Dell\u2019Olmo, P., Kellerer, H., Speranza, M.G., Tuza, Z.: A 13\/12 approximation algorithm for bin packing with extendable bins. Inf. Process. Lett. 65(5), 229\u2013233 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"8_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0166-218X(99)00020-7","volume":"4","author":"P Dell\u2019Olmo","year":"1999","unstructured":"Dell\u2019Olmo, P., Speranza, M.G.: Approximation algorithms for partitioning small items in unequal bins to minimize the total size. Discret. Appl. Math. 4(1\u20133), 181\u2013191 (1999)","journal-title":"Discret. Appl. Math."},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00236-005-0003-7","volume":"42","author":"L Epstein","year":"2006","unstructured":"Epstein, L., Tassa, T.: Vector assignment schemes for asymmetric settings. Acta Informatica 42, 501\u2013514 (2006)","journal-title":"Acta Informatica"},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessor timing anomalies. SIAM J. Appl. Math. 17(2), 416\u201329 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"8_CR11","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., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"8_CR12","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"issue":"12","key":"8_CR13","doi-asserted-by":"publisher","first-page":"2055","DOI":"10.1016\/S0305-0548(03)00164-3","volume":"31","author":"HC Hwang","year":"2004","unstructured":"Hwang, H.C., Chang, S.Y., Lee, K.: Parallel machine scheduling under a grade of service provision. Comput. Oper. Res. 31(12), 2055\u20132061 (2004)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.ipl.2008.04.021","volume":"108","author":"M Ji","year":"2008","unstructured":"Ji, M., Cheng, T.C.E.: An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan. Inf. Process. Lett. 108(4), 171\u2013174 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s10878-007-9095-z","volume":"16","author":"Y Jiang","year":"2008","unstructured":"Jiang, Y.: Online scheduling on parallel machines with two GoS levels. J. Comb. Optim. 16(1), 28\u201338 (2008)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"8_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s00453-021-00895-8","volume":"84","author":"A Levin","year":"2022","unstructured":"Levin, A.: Approximation schemes for the generalized extensible bin packing problem. Algorithmica 84(2), 325\u2013343 (2022)","journal-title":"Algorithmica"},{"issue":"03","key":"8_CR17","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1142\/S1793830909000282","volume":"1","author":"J Li","year":"2009","unstructured":"Li, J., Li, W., Li, J.: Polynomial approximation schemes for the max-min allocation problem under a grade of service provision. Discrete Math. Algorithms Appl. 1(03), 355\u2013368 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"issue":"4","key":"8_CR18","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1002\/nav.20286","volume":"55","author":"J Ou","year":"2008","unstructured":"Ou, J., Leung, J.Y.T., Li, C.L.: Scheduling parallel machines with inclusive processing set restrictions. Nav. Res. Logist. 55(4), 328\u2013338 (2008)","journal-title":"Nav. Res. Logist."},{"issue":"6","key":"8_CR19","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1016\/j.orl.2005.11.004","volume":"34","author":"J Park","year":"2006","unstructured":"Park, J., Chang, S.Y., Lee, K.: Online and semi-online scheduling of two machines under a grade of service provision. Oper. Res. Lett. 34(6), 692\u2013696 (2006)","journal-title":"Oper. Res. Lett."},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1023\/A:1018935608981","volume":"86","author":"MG Speranza","year":"1999","unstructured":"Speranza, M.G., Tuza, Z.: On-line approximation algorithms for scheduling tasks on identical machines withextendable working time. Ann. Oper. Res. 86, 491\u2013506 (1999)","journal-title":"Ann. Oper. Res."},{"key":"8_CR21","first-page":"1","volume":"74","author":"Q Wei","year":"2022","unstructured":"Wei, Q., Wu, Y., Cheng, T.C.E., Sun, F., Jiang, Y.: Online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time. J. Oper. Res. Soc. 74, 1\u201323 (2022)","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"8_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"G Woeginger","year":"2000","unstructured":"Woeginger, G.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57\u201374 (2000)","journal-title":"INFORMS J. Comput."},{"key":"8_CR23","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-981-13-2712-4_1","volume-title":"Theoretical Computer Science","author":"G Wu","year":"2018","unstructured":"Wu, G., Li, W.: Semi-online machine covering on two hierarchical machines with discrete processing times. In: Li, L., Lu, P., He, K. (eds.) NCTCS 2018. CCIS, vol. 882, pp. 1\u20137. Springer, Singapore (2018). https:\/\/doi.org\/10.1007\/978-981-13-2712-4_1"},{"key":"8_CR24","unstructured":"Xiao, M., Liu, X., Li, W., Chen, X., Sterna, M., Blazewicz, J.: Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work. arXiv preprint arXiv:2209.08704, https:\/\/doi.org\/10.48550\/arXiv.2209.08704 (2022)"},{"key":"8_CR25","doi-asserted-by":"publisher","unstructured":"Xiao, M., Li, W.: Online early work maximization on three hierarchical machines with a common due date. In: Li, M., Sun, X. (eds.) Frontiers of Algorithmic Wisdom. IJTCS-FAW 2022. LNCS, vol. 13461, pp. 99\u2013109. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-20796-9_8","DOI":"10.1007\/978-3-031-20796-9_8"},{"key":"8_CR26","doi-asserted-by":"publisher","unstructured":"Xiao, M., Du, Y., Li, W., Yang, J.: Semi-online machine covering problem on three hierarchical machines with bounded processing times. J. Oper. Res. Soc. China 1\u201313 (2023). https:\/\/doi.org\/10.1007\/s40305-023-00477-1","DOI":"10.1007\/s40305-023-00477-1"},{"issue":"1","key":"8_CR27","first-page":"141","volume":"11","author":"D Ye","year":"2009","unstructured":"Ye, D., Zhang, G.: On-line extensible bin packing with unequal bin sizes. Discrete Math. Theor. Comput. Sci. 11(1), 141\u2013152 (2009)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"38\u201340","key":"8_CR28","doi-asserted-by":"publisher","first-page":"3597","DOI":"10.1016\/j.tcs.2009.04.007","volume":"410","author":"A Zhang","year":"2009","unstructured":"Zhang, A., Jiang, Y., Tan, Z.: Online parallel machines scheduling with two hierarchies. Theoret. Comput. Sci. 410(38\u201340), 3597\u20133605 (2009)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Communications in Computer and Information Science","Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-99-7743-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T09:04:52Z","timestamp":1700903092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-99-7743-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,26]]},"ISBN":["9789819977420","9789819977437"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-981-99-7743-7_8","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2023,11,26]]},"assertion":[{"value":"26 November 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"NCTCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"National Conference of Theoretical Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guangzhou","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":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"nctcs2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.ccf.org.cn\/TCS2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"https:\/\/conf.ccf.org.cn\/TCS2023","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"70","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The submission system is belonged to the hosted organization -China Computer Federation. It is free to us.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}