{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:34:04Z","timestamp":1767339244179,"version":"build-2065373602"},"reference-count":43,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["12071417","KC-22223092"],"award-info":[{"award-number":["12071417","KC-22223092"]}]},{"DOI":"10.13039\/501100007839","name":"Postgraduate Research and Innovation Foundation of Yunnan University","doi-asserted-by":"publisher","award":["12071417","KC-22223092"],"award-info":[{"award-number":["12071417","KC-22223092"]}],"id":[{"id":"10.13039\/501100007839","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>In this paper, we consider two types of semi-online problems with hierarchies. In the extensible bin-packing problem with two hierarchical bins, one bin can pack all items, while the other bin can only pack some items. The initial size of the bin can be expanded, and the goal is to minimize the total size of the two bins. When the largest item size is given in advance, we provide some lower bounds and propose online algorithms. When the total item size is given in advance, we provide some lower bounds and propose online algorithms. In addition, we also consider the relevant early-work-maximization problem on two hierarchical machines; one machine can process any job, while the other machine can only process some jobs. Each job shares a common due date, and the goal is to maximize the total early work. When the largest job size is known, we provide some lower bounds and propose two online algorithms whose competitive ratios are close to the lower bounds.<\/jats:p>","DOI":"10.3390\/computation12040068","type":"journal-article","created":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T01:26:10Z","timestamp":1712021170000},"page":"68","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Semi-Online Algorithms for the Hierarchical Extensible Bin-Packing Problem and Early Work Problem"],"prefix":"10.3390","volume":"12","author":[{"given":"Yaru","family":"Yang","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2443-6768","authenticated-orcid":false,"given":"Man","family":"Xiao","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming 650504, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,4,1]]},"reference":[{"key":"ref_1","unstructured":"Coffman, E.G., Csirik, J., Galambos, G., Martello, S., and Vigo, D. (2013). Handbook of Combinatorial Optimization, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Hoberg, R., and Rothvoss, T. (2017, January 16\u201319). A logarithmic additive integrality gap for bin packing. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.172"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1023\/A:1018935608981","article-title":"On-line approximation algorithms for scheduling tasks on identical machines with extendable working time","volume":"86","author":"Speranza","year":"1999","journal-title":"Ann. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10878-023-01086-7","article-title":"Semi-online early-work-maximization problems on two hierarchical uniform machines with partial information of processing time","volume":"46","author":"Xiao","year":"2023","journal-title":"J. Comb. Optim."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3535","DOI":"10.1007\/s10878-022-00906-6","article-title":"Online scheduling with migration on two hierarchical machines","volume":"44","author":"Akaria","year":"2022","journal-title":"J. Comb. Optim."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1950002","DOI":"10.1142\/S0217595919500027","article-title":"Semi-online hierarchical scheduling on two machines for lp-norm load balancing","volume":"36","author":"Qi","year":"2019","journal-title":"Asia Pac. J. Oper. Res."},{"key":"ref_7","unstructured":"Xiao, M., Liu, X., Li, W., Chen, X., Sterna, M., and Blazewicz, J. (2022). Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0020-0190(97)00216-0","article-title":"A 13\/12 approximation algorithm for bin packing with extendable bins","volume":"65","author":"Kellerer","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1287\/opre.1090.0791","article-title":"Optimal allocation of surgery blocks to operating rooms under uncertainty","volume":"58","author":"Denton","year":"2010","journal-title":"J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","article-title":"Approximation schemes for scheduling on parallel machines","volume":"1","author":"Alon","year":"1998","journal-title":"J. Sched."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10951-006-5594-5","article-title":"Approximation algorithms for extensible bin packing","volume":"9","author":"Coffman","year":"2006","journal-title":"J. Sched."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","article-title":"When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?","volume":"12","author":"Woeginger","year":"2000","journal-title":"INFORMS J. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s00453-021-00895-8","article-title":"Approximation schemes for the generalized extensible bin-packing problem","volume":"84","author":"Levin","year":"2022","journal-title":"Algorithmica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0166-218X(99)00020-7","article-title":"Approximation algorithms for partitioning small items in unequal bins to minimize the total size","volume":"94","author":"Speranza","year":"1999","journal-title":"Discret. Appl. Math."},{"key":"ref_15","unstructured":"Ye, D., and Zhang, G. (2019, January 16\u201318). On-line extensible bin packing with unequal bin sizes. Proceedings of the 1st International Workshop on Approximation and Online Algorithms, Budapest, Hungary."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1287\/ijoc.2017.0750","article-title":"Fast approximation methods for online scheduling of outpatient procedure centers","volume":"29","author":"Berg","year":"2017","journal-title":"INFORMS J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Luo, K., and Spieksma, F.C.R. (2021, January 11\u201313). Online bin packing with overload cost. Proceedings of the 7th International Conference on Algorithms and Discrete Applied Mathematics, Rupnagar, India.","DOI":"10.1007\/978-3-030-67899-9_1"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0020-0190(02)00404-0","article-title":"On-line scheduling with extendable working time on a small number of machines","volume":"85","author":"Ye","year":"2003","journal-title":"Inform. Process. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Sagnol, G., Schmidt genannt Waldschmidt, D., and Tesch, A. (2018, January 23\u201324). The price of fixed assignments in stochastic extensible bin packing. Proceedings of the 16th International Workshop on Approximation and Online Algorithms, Helsinki, Finland.","DOI":"10.1007\/978-3-030-04693-4_20"},{"key":"ref_20","unstructured":"Sagnol, G. (2020). Stochastic extensible bin packing. arXiv."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sagnol, G., and Schmidt genannt Waldschmidt, D. (2022, January 18\u201320). Improved bounds for stochastic extensible bin packing under distributional assumptions. Proceedings of the 7th International Symposium on Combinatorial Optimization, Online.","DOI":"10.1007\/978-3-031-18530-4_17"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1080\/00207160.2014.922682","article-title":"Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs","volume":"92","author":"Chen","year":"2015","journal-title":"Int. J. Comput. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"5762340","DOI":"10.1155\/2014\/576234","article-title":"Semi-online scheduling on two machines with GoS levels and partial information of processing time","volume":"2014","author":"Luo","year":"2014","journal-title":"Sci. World J."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Li, W. (2022). Improved approximation schemes for early work scheduling on identical parallel machines with a common due date. J. Oper. Res. Soc. China, online.","DOI":"10.1007\/s40305-022-00402-y"},{"key":"ref_25","unstructured":"Sun, R., Zhang, R., Lan, Y., and Li, W. (2024). LPT algorithm for early-work-maximization problem. Oper. Res. Trans., Available online: https:\/\/kns.cnki.net\/kcms\/detail\/31.1732.O1.20240129.1642.008.html."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10951-015-0464-7","article-title":"Scheduling on parallel identical machines with late work criterion: Offline and online cases","volume":"92","author":"Chen","year":"2016","journal-title":"J. Sched."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1016\/j.ejor.2024.01.009","article-title":"Online early work scheduling on parallel machines","volume":"315","author":"Jiang","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Xiao, M., Bai, X., and Li, W. (2022, January 13\u201314). Online early-work-maximization problem on two hierarchical machines with buffer or rearrangements. Proceedings of the 16th International Conference on Algorithmic Applications in Management, Guangzhou, China.","DOI":"10.1007\/978-3-031-16081-3_5"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s10288-016-0334-y","article-title":"Semi-online hierarchical scheduling for lp-norm load balancing with buffer or rearrangements","volume":"15","author":"Qi","year":"2017","journal-title":"4OR"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/s10878-007-9078-0","article-title":"The hierarchical model for load balancing on two machines","volume":"15","author":"Chassid","year":"2008","journal-title":"J. Comb. Optim."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.tcs.2015.03.050","article-title":"Semi-online hierarchical load balancing problem with bounded processing times","volume":"607","author":"Luo","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2014.02.015","article-title":"Optimal algorithms for semi-online machine covering on two hierarchical machines","volume":"531","author":"Wu","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"105646","DOI":"10.1016\/j.cor.2021.105646","article-title":"Semi-online scheduling: A survey","volume":"139","author":"Dwibedy","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"7061","DOI":"10.3934\/math.2023356","article-title":"On preemptive scheduling of unrelated machines using linear programming","volume":"8","author":"Vakhania","year":"2023","journal-title":"AIMS Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"19427","DOI":"10.3934\/math.2023991","article-title":"Single machine and group scheduling with random learning rates","volume":"8","author":"Wang","year":"2023","journal-title":"AIMS Math."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1016\/j.orl.2005.11.004","article-title":"Online and semi-online scheduling of two machines under a grade of service provision","volume":"34","author":"Park","year":"2006","journal-title":"Oper. Res. Lett."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1631\/jzus.2006.A0309","article-title":"Optimal online algorithms for scheduling on two identical machines under a grade of service","volume":"7","author":"Jiang","year":"2006","journal-title":"J. Zhejiang Univ.-Sci. A"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.ijpe.2011.07.021","article-title":"Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision","volume":"135","author":"Wu","year":"2012","journal-title":"Int. J. Prod. Econ."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/s10878-009-9231-z","article-title":"Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times","volume":"21","author":"Liu","year":"2011","journal-title":"J. Comb. Optim."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s11590-014-0838-3","article-title":"Optimal algorithm for semi-online scheduling on two machines under GoS levels","volume":"10","author":"Luo","year":"2016","journal-title":"Optim. Lett."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1007\/s10878-013-9627-7","article-title":"Optimal online algorithms on two hierarchical machines with tightly-grouped processing times","volume":"29","author":"Zhang","year":"2015","journal-title":"J. Comb. Optim."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.ipl.2012.12.007","article-title":"Semi-online hierarchical scheduling problems with buffer or rearrangement","volume":"113","author":"Chen","year":"2013","journal-title":"Inform. Process. Lett."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1137\/S0097539798346135","article-title":"On-line load balancing in a hierarchical server topology","volume":"31","author":"Freund","year":"2001","journal-title":"SIAM J. Comput."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/12\/4\/68\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:22:18Z","timestamp":1760106138000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/12\/4\/68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,1]]},"references-count":43,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["computation12040068"],"URL":"https:\/\/doi.org\/10.3390\/computation12040068","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2024,4,1]]}}}