{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:38:59Z","timestamp":1740145139282,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:00:00Z","timestamp":1675296000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:00:00Z","timestamp":1675296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11501171","11771251"],"award-info":[{"award-number":["11501171","11771251"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s11590-022-01966-7","type":"journal-article","created":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T16:22:25Z","timestamp":1675354945000},"page":"319-338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A best possible online algorithm for minimizing the total completion time and the total soft penalty cost"],"prefix":"10.1007","volume":"18","author":[{"given":"Ran","family":"Ma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juannian","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,2]]},"reference":[{"key":"1966_CR1","doi-asserted-by":"crossref","unstructured":"Anand, S., Garg, N., Kumar, A.: Resource augmentation for weighted flow-time explained by dual fitting. In: Proceedings of Symposium on Discrete Algorithms (SODA), pp. 1228\u20131241 (2012)","DOI":"10.1137\/1.9781611973099.97"},{"key":"1966_CR2","doi-asserted-by":"publisher","first-page":"3391","DOI":"10.1007\/s00453-019-00583-8","volume":"81","author":"S Angelopoulos","year":"2019","unstructured":"Angelopoulos, S., Lucarelli, G., Thang, N.K.: Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems. Algorithmica.\u00a081, 3391\u20133421 (2019)","journal-title":"Algorithmica."},{"key":"1966_CR3","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ejor.2019.10.004","volume":"282","author":"P Alfaro-Fern\u00e1ndez","year":"2020","unstructured":"Alfaro-Fern\u00e1ndez, P., Ruiz, R., Pagnozzi, F., St\u00fctzle, T.: Automatic algorithm design for hybrid flowshop scheduling problems. Eur. J. Oper. Res. 282, 835\u2013845 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"1966_CR4","volume-title":"Introduction to Sequencing and Scheduling","author":"KR Baker","year":"1974","unstructured":"Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974)"},{"key":"1966_CR5","unstructured":"Bansal, N., Dhamdhere, K.: Minimizing weighted flow time. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 508\u2013516 (2003)"},{"key":"1966_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.L.: Weighted flow time does not admit o(1)-competitive algorithms. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1238\u20131244 (2009)","DOI":"10.1137\/1.9781611973068.134"},{"issue":"3","key":"1966_CR7","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10951-014-0380-2","volume":"18","author":"O Bellenguez-Morineau","year":"2015","unstructured":"Bellenguez-Morineau, O., Chrobak, M., D\u00fcrr, C., Prot, D.: A note on NP-hardness of preemptive mean flow-time scheduling for parallel machines. J. Sched. 18(3), 299\u2013304 (2015)","journal-title":"J. Sched."},{"key":"1966_CR8","volume-title":"Theory of Scheduling","author":"RW Conway","year":"1967","unstructured":"Conway, R.W., Maxwell, W.C., Miller, L.W.: Theory of Scheduling. Addison-Wesley, New York (1967)"},{"key":"1966_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), pp. 84\u201393 (2001)","DOI":"10.1145\/380752.380778"},{"key":"1966_CR10","doi-asserted-by":"crossref","unstructured":"Choudhury, A.R., Das, S., Garg, N., Kumar, A.: Rejecting jobs to minimize load and maximum flow-time. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1114\u20131133 (2015)","DOI":"10.1137\/1.9781611973730.75"},{"key":"1966_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2021.104375","volume":"104","author":"S Chen","year":"2021","unstructured":"Chen, S., Pan, Q.K., Gao, L., Sang, H.Y.: A population-based iterated greedy algorithm to minimize total flowtime for the distributed blocking flowshop scheduling problem. Eng. Appl. Artif. Intell. 104, 104375 (2021)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"1966_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2019.05.007","volume":"81","author":"GL Deng","year":"2019","unstructured":"Deng, G.L., Zhang, Z.W., Jiang, T.H., Zhang, S.N.: Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer. Appl. Soft Comput. 81, 105480 (2019)","journal-title":"Appl. Soft Comput."},{"key":"1966_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2019.103369","volume":"88","author":"GL Deng","year":"2020","unstructured":"Deng, G.L., Su, Q.T., Zhang, Z.W., Liu, H.X., Zhang, S.N., Jiang, T.H.: A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion. Eng. Appl. Artif. Intel. 88, 103369 (2020)","journal-title":"Eng. Appl. Artif. Intel."},{"key":"1966_CR14","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Moseley, B.: Scheduling for weighted flow and completion times in reconfigurable networks. In: IEEE Conference on Computer Communications(INFOCOM), pp. 1043\u20131052 (2020)","DOI":"10.1109\/INFOCOM41043.2020.9155537"},{"issue":"9","key":"1966_CR15","doi-asserted-by":"publisher","first-page":"3746","DOI":"10.1007\/s00453-019-00597-2","volume":"81","author":"K Fox","year":"2019","unstructured":"Fox, K., Im, S., Kulkarni, J., Moseley, B.: Non-clairvoyantly scheduling to minimize convex functions. Algorithmica.\u00a081(9), 3746\u20133764 (2019)","journal-title":"Algorithmica."},{"key":"1966_CR16","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.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"key":"1966_CR17","doi-asserted-by":"crossref","unstructured":"Hoogeveen, J.A., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 404\u2013414 (1996)","DOI":"10.1007\/3-540-61310-2_30"},{"issue":"6","key":"1966_CR18","doi-asserted-by":"publisher","first-page":"2472","DOI":"10.1109\/TNET.2019.2953806","volume":"27","author":"ZH Han","year":"2019","unstructured":"Han, Z.H., Tan, H.S., Li, X.Y., Jiang, S.H.C., Li, Y.P., Lau, F.C.M.: OnDisc: Online latency-sensitive job dispatching and scheduling in heterogeneous edge-clouds. IEEE\/ACM Trans. Netw. 27(6), 2472\u20132485 (2019)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"1","key":"1966_CR19","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1137\/120902288","volume":"43","author":"S Im","year":"2014","unstructured":"Im, S., Moseley, B., Pruhs, K.: Online scheduling with general cost functions. SIAM J. Comput. 43(1), 126\u2013143 (2014)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1966_CR20","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.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM J. Comput. 28(4), 1155\u20131166 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1966_CR21","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM.\u00a047(4), 617\u2013643 (2000)","journal-title":"J. ACM."},{"issue":"4","key":"1966_CR22","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., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1(4), 343\u2013362 (1977)","journal-title":"Ann. Discrete Math."},{"key":"1966_CR23","unstructured":"Lucarelli, G., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling in a resource augmentation model based on duality. In: European Symposium on Algorithms (ESA), pp. 1\u201317 (2016)"},{"key":"1966_CR24","doi-asserted-by":"crossref","unstructured":"Lucarelli, G., Moseley, B., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling on unrelated machines with rejections. In: ACM Symposium on Parellelism in Algorithms and Architectures (SPAA) (2018)","DOI":"10.1145\/3210377.3210402"},{"key":"1966_CR25","unstructured":"Lucarelli, G., Moseley, B., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling to minimize weighted flow-time on unrelated machines. In: 26th Annual European Symposium on Algorithms (ESA ), pp. 1\u201312 (2018)"},{"key":"1966_CR26","unstructured":"Lucarelli, G., Moseley, B., Thang, N.K., Srivastav, A., Trystram, D.: Online non-preemptive scheduling to minimize maximum weighted flow-time on related machines. In: FSTTCS (2019)"},{"key":"1966_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2021.100874","volume":"63","author":"Y-Z Li","year":"2021","unstructured":"Li, Y.-Z., Pan, Q.-K., Li, J.-Q., Gao, L., Tasgetiren, M.F.: An adaptive iterated greedy algorithm for distributed mixed no-idle permutation flowshop scheduling problems. Swarm Evol. Comput. 63, 100874 (2021)","journal-title":"Swarm Evol. Comput."},{"key":"1966_CR28","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ejor.2020.08.009","volume":"290","author":"R Ma","year":"2021","unstructured":"Ma, R., Guo, S.N.: Applying \u201cPeeling Onion\u2019\u2019 approach for competitive analysis in online scheduling with rejection. Eur. J. Oper. Res. 290, 57\u201367 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"1966_CR29","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.cor.2019.06.009","volume":"111","author":"H \u00d6ztop","year":"2019","unstructured":"\u00d6ztop, H., Tasgetiren, M.F., Eliiyi, D.T., Pan, Q.-K.: Metaheuristic algorithms for the hybrid flowshop scheduling problem. Comput. Oper. Res. 111, 177\u2013196 (2019)","journal-title":"Comput. Oper. Res."},{"key":"1966_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113279","volume":"150","author":"H \u00d6ztop","year":"2020","unstructured":"\u00d6ztop, H., Tasgetiren, M.F., Eliiyi, D.T., Pan, Q.-K., Kandiller, L.K.: An energy-efficient permutation flowshop scheduling problem. Expert Syst. Appl. 150, 113279 (2020)","journal-title":"Expert Syst. Appl."},{"key":"1966_CR31","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/j.ejor.2020.03.044","volume":"286","author":"O Ozturk","year":"2020","unstructured":"Ozturk, O.: A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time. Eur. J. Oper. Res. 286, 432\u2013443 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1966_CR32","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica.\u00a032(2), 163\u2013200 (2002)","journal-title":"Algorithmica."},{"key":"1966_CR33","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.eswa.2019.01.062","volume":"124","author":"Q-K Pan","year":"2019","unstructured":"Pan, Q.-K., Gao, L., Wang, L., Liang, J., Li, X.-Y.: Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem. Expert Syst. Appl. 124, 309\u2013324 (2019)","journal-title":"Expert Syst. Appl."},{"key":"1966_CR34","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single stage production. Naval Res. Logist. Quart. 3, 59\u201366 (1956)","journal-title":"Naval Res. Logist. Quart."},{"key":"1966_CR35","doi-asserted-by":"crossref","unstructured":"Zhao, Z.Y., Zhou, M.C., Liu, S.X.: Iterated greedy algorithms for flow-shop scheduling problems: a tutorial. IEEE Trans. Autom. Sci. Eng. (2021)","DOI":"10.1109\/TASE.2021.3062994"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01966-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01966-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01966-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T06:21:55Z","timestamp":1704867715000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01966-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,2]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1966"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01966-7","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2023,2,2]]},"assertion":[{"value":"1 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}