{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T01:20:32Z","timestamp":1773883232275,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Macedonia. Library"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We address in this paper the parallel machine scheduling problem with a shared loading server and a shared unloading server. Each job has to be loaded by the loading server before being processed on one of the available machines and unloaded immediately by the unloading server after its processing. The objective function involves the minimization of the overall completion time, known as the makespan. This important problem raises in flexible manufacturing systems, automated material handling, healthcare, and many other industrial fields, and has been little studied up to now. To date, research on it has focused on the case of two machines. The regular case of this problem is considered. A mixed integer programming formulation based on completion time variables is suggested to solve small-sized instances of the problem. Due to its <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{NP}\\mathcal{}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>NP<\/mml:mi>\n                    <mml:mrow\/>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hardness, we propose two greedy heuristics based on the minimization of the loading, respectively unloading, server waiting time, and an efficient General Variable Neighborhood Search (GVNS) algorithm. In the computational experiments, the proposed methods are compared using 120 new and publicly available instances. It turns out that, the proposed GVNS with an initial solution-finding mechanism based on the unloading server waiting time minimization significantly outperforms the other approaches.<\/jats:p>","DOI":"10.1007\/s11590-022-01925-2","type":"journal-article","created":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T08:20:45Z","timestamp":1662798045000},"page":"2201-2231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["General variable neighborhood search for the parallel machine scheduling problem with two common servers"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5024-6610","authenticated-orcid":false,"given":"Abdelhak","family":"Elidrissi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2553-4116","authenticated-orcid":false,"given":"Rachid","family":"Benmansour","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5696-7021","authenticated-orcid":false,"given":"Angelo","family":"Sifaleras","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,10]]},"reference":[{"issue":"3","key":"1925_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0305-0548(00)00074-5","volume":"29","author":"AH Abdekhodaee","year":"2002","unstructured":"Abdekhodaee, A.H., Wirth, A.: Scheduling parallel machines with a single server: some solvable cases and heuristics. Comput. Oper. Res. 29(3), 295\u2013315 (2002)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"1925_CR2","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1016\/j.cor.2004.08.013","volume":"33","author":"AH Abdekhodaee","year":"2006","unstructured":"Abdekhodaee, A.H., Wirth, A., Gan, H.S.: Scheduling two parallel machines with a single server: the general case. Comput. Oper. Res. 33(4), 994\u20131009 (2006)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1925_CR3","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1016\/j.ejor.2006.09.010","volume":"187","author":"A Allahverdi","year":"2008","unstructured":"Allahverdi, A., Soroush, H.: The significance of reducing setup times\/setup costs. Eur. J. Oper. Res. 187(3), 978\u2013984 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"1925_CR4","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.cie.2010.07.028","volume":"59","author":"KR Baker","year":"2010","unstructured":"Baker, K.R., Keller, B.: Solving the single-machine sequencing problem using integer programming. Comput. Ind. Eng. 59(4), 730\u2013735 (2010)","journal-title":"Comput. Ind. Eng."},{"key":"1925_CR5","doi-asserted-by":"crossref","unstructured":"Balas, E.: On the facial structure of scheduling polyhedra. In: Mathematical Programming Essays in Honor of George B. Dantzig Part I, pp. 179\u2013218. Springer (1985)","DOI":"10.1007\/BFb0121051"},{"key":"1925_CR6","doi-asserted-by":"crossref","unstructured":"Bektur, G., Sarac\u0327, T,: A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Comput. Oper. Res. 103, 46\u201363 (2019)","DOI":"10.1016\/j.cor.2018.10.010"},{"key":"1925_CR7","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.cor.2014.02.004","volume":"47","author":"R Benmansour","year":"2014","unstructured":"Benmansour, R., Allaoui, H., Artiba, A., Hanafi, S.: Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance. Comput. Oper. Res. 47, 106\u2013113 (2014)","journal-title":"Comput. Oper. Res."},{"key":"1925_CR8","doi-asserted-by":"crossref","unstructured":"Benmansour, R., Sifaleras, A.: Scheduling in parallel machines with two servers: the restrictive case. In: Variable Neighborhood Search: 8th International Conference, ICVNS 2021, Abu Dhabi, United Arab Emirates, 21\u201325 March, 2021, Proceedings 8, pp. 71\u201382. Springer International Publishing (2021)","DOI":"10.1007\/978-3-030-69625-2_6"},{"issue":"1","key":"1925_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0377-2217(01)00382-4","volume":"144","author":"EK Bish","year":"2003","unstructured":"Bish, E.K.: A multiple-crane-constrained scheduling problem in a container terminal. Eur. J. Oper. Res. 144(1), 83\u2013107 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"1925_CR10","doi-asserted-by":"crossref","unstructured":"Brimberg, J., Uros\u030cevi\u0107, D., Mladenovi\u0107, N,: Variable neighborhood search for the vertex weighted k-cardinality tree problem. Eur. J. Oper. Res. 171(1), 74\u201384 (2006)","DOI":"10.1016\/j.ejor.2004.07.061"},{"key":"1925_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, T., Kravchenko, S.A., Lin, B.M.: Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences. J. Oper. Res. Soc. 1\u20134 (2020)","DOI":"10.1002\/nav.21846"},{"key":"1925_CR12","doi-asserted-by":"publisher","first-page":"104886","DOI":"10.1016\/j.cor.2020.104886","volume":"117","author":"ROM Diana","year":"2020","unstructured":"Diana, R.O.M., de Souza, S.R.: Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines. Comput. Oper. Res. 117, 104886 (2020)","journal-title":"Comput. Oper. Res."},{"key":"1925_CR13","first-page":"1","volume-title":"Handbook of heuristics","author":"A Duarte","year":"2016","unstructured":"Duarte, A., Mladenovi\u0107, N., S\u00e1nchez-Oro, J., Todosijevi\u0107, R.: Variable Neighborhood Descent. In: Mart\u00ed, R., Panos, P., Resende, M.G. (eds.) Handbook of heuristics, pp. 1\u201327. Springer International Publishing, Cham (2016)"},{"key":"1925_CR14","doi-asserted-by":"crossref","unstructured":"El\u00a0Idrissi, A., Benbrahim, M., Benmansour, R., Duvivier, D.: Greedy heuristics for identical parallel machine scheduling problem with single server to minimize the makespan. In: MATEC Web of Conferences, vol. 200, p. 00001. EDP Sciences (2018)","DOI":"10.1051\/matecconf\/201820000001"},{"key":"1925_CR15","doi-asserted-by":"crossref","unstructured":"Elidrissi, A., Benbrahim, M., Benmansour, R., Duvivier, D.: Variable neighborhood search for identical parallel machine scheduling problem with a single server. In: International Conference on Variable Neighborhood Search, pp. 112\u2013125. Springer (2019)","DOI":"10.1007\/978-3-030-44932-2_8"},{"issue":"20","key":"1925_CR16","doi-asserted-by":"publisher","first-page":"6166","DOI":"10.1080\/00207543.2020.1807637","volume":"59","author":"A Elidrissi","year":"2021","unstructured":"Elidrissi, A., Benmansour, R., Benbrahim, M., Duvivier, D.: Mathematical formulations for the parallel machine scheduling problem with a single server. Int. J. Prod. Res. 59(20), 6166\u20136184 (2021)","journal-title":"Int. J. Prod. Res."},{"key":"1925_CR17","doi-asserted-by":"crossref","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics, vol.\u00a05, pp. 287\u2013326. Elsevier (1979)","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"1925_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.cie.2017.02.013","volume":"106","author":"A Hamzadayi","year":"2017","unstructured":"Hamzadayi, A., Yildiz, G.: Modeling and solving static $$m$$ identical parallel machines scheduling problem with a common server and sequence dependent setup times. Comput. Ind. Eng. 106, 287\u2013298 (2017)","journal-title":"Comput. Ind. Eng."},{"issue":"1","key":"1925_CR19","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10479-009-0657-6","volume":"175","author":"P Hansen","year":"2010","unstructured":"Hansen, P., Mladenovi\u0107, N., P\u00e9rez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175(1), 367\u2013407 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"1925_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s13675-016-0075-x","volume":"5","author":"P Hansen","year":"2017","unstructured":"Hansen, P., Mladenovi\u0107, N., Todosijevi\u0107, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423\u2013454 (2017)","journal-title":"EURO J. Comput. Optim."},{"issue":"13","key":"1925_CR21","doi-asserted-by":"publisher","first-page":"3778","DOI":"10.1080\/00207543.2013.874607","volume":"52","author":"K Hasani","year":"2014","unstructured":"Hasani, K., Kravchenko, S.A., Werner, F.: Simulated annealing and genetic algorithms for the two-machine scheduling problem with a single server. Int. J. Prod. Res. 52(13), 3778\u20133792 (2014)","journal-title":"Int. J. Prod. Res."},{"issue":"1","key":"1925_CR22","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1080\/0305215X.2015.1005083","volume":"48","author":"K Hasani","year":"2016","unstructured":"Hasani, K., Kravchenko, S.A., Werner, F.: Minimizing the makespan for the two-machine scheduling problem with a single server: two algorithms for very large instances. Eng. Optim. 48(1), 173\u2013183 (2016)","journal-title":"Eng. Optim."},{"issue":"6","key":"1925_CR23","doi-asserted-by":"publisher","first-page":"640","DOI":"10.3390\/healthcare9060640","volume":"9","author":"PY Hsu","year":"2021","unstructured":"Hsu, P.Y., Lo, S.H., Hwang, H.G., Lin, B.M.: Scheduling of anaesthesia operations in operating rooms. Healthcare 9(6), 640 (2021)","journal-title":"Healthcare"},{"issue":"1","key":"1925_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.cie.2009.10.003","volume":"58","author":"S Huang","year":"2010","unstructured":"Huang, S., Cai, L., Zhang, X.: Parallel dedicated machine scheduling problem with sequence-dependent setups and a single server. Comput. Ind. Eng. 58(1), 165\u2013174 (2010)","journal-title":"Comput. Ind. Eng."},{"issue":"5","key":"1925_CR25","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1111\/itor.12136","volume":"22","author":"Y Jiang","year":"2015","unstructured":"Jiang, Y., Yu, F., Zhou, P., Hu, J.: Online algorithms for scheduling two parallel machines with a single server. Int. Trans. Oper. Res. 22(5), 913\u2013927 (2015)","journal-title":"Int. Trans. Oper. Res."},{"issue":"3\u20134","key":"1925_CR26","first-page":"314","volume":"58","author":"Y Jiang","year":"2017","unstructured":"Jiang, Y., Zhou, P., Wang, H., Hu, J.: Scheduling on two parallel machines with two dedicated servers. ANZIAM J. 58(3\u20134), 314\u2013323 (2017)","journal-title":"ANZIAM J."},{"issue":"11","key":"1925_CR27","doi-asserted-by":"publisher","first-page":"2457","DOI":"10.1016\/j.cor.2011.12.011","volume":"39","author":"MY Kim","year":"2012","unstructured":"Kim, M.Y., Lee, Y.H.: Mip models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Comput. Oper. Res. 39(11), 2457\u20132468 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"10","key":"1925_CR28","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1016\/0305-0548(96)00011-1","volume":"23","author":"CP Koulamas","year":"1996","unstructured":"Koulamas, C.P.: Scheduling two parallel semiautomatic machines to minimize machine interference. Comput. Oper. Res. 23(10), 945\u2013956 (1996)","journal-title":"Comput. Oper. Res."},{"key":"1925_CR29","unstructured":"Kravchenko, S.A., Werner, F.: Scheduling on parallel machines with a single and multiple servers. Otto-von-Guericke-Universitat Magdeburg 30(98), 1\u201318 (1998)"},{"issue":"3","key":"1925_CR30","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1111\/itor.12282","volume":"24","author":"A Mjirda","year":"2017","unstructured":"Mjirda, A., Todosijevi\u0107, R., Hanafi, S., Hansen, P., Mladenovi\u0107, N.: Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. Int. Trans. Oper. Res. 24(3), 615\u2013633 (2017)","journal-title":"Int. Trans. Oper. Res."},{"issue":"11","key":"1925_CR31","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097\u20131100 (1997)","journal-title":"Comput. Oper. Res."},{"key":"1925_CR32","doi-asserted-by":"crossref","unstructured":"Mladenovi\u0107, N., Sleptchenko, A., Sifaleras, A., Omar, M. (eds.): Variable neighborhood search. In: 8th International Conference, ICVNS 2021, Abu Dhabi, United Arab Emirates, 21\u201325 October, 2021, Revised Selected Papers, LNCS, vol. 12559. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-69625-2"},{"issue":"3","key":"1925_CR33","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s10951-009-0104-1","volume":"13","author":"J Ou","year":"2010","unstructured":"Ou, J., Qi, X., Lee, C.Y.: Parallel machine scheduling with multiple unloading servers. J. Sched. 13(3), 213\u2013226 (2010)","journal-title":"J. Sched."},{"issue":"2","key":"1925_CR34","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1080\/01605682.2019.1671153","volume":"72","author":"JMP Silva","year":"2021","unstructured":"Silva, J.M.P., Teixeira, E., Subramanian, A.: Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times. J. Oper. Res. Soc. 72(2), 444\u2013457 (2021)","journal-title":"J. Oper. Res. Soc."},{"issue":"3","key":"1925_CR35","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s10100-015-0395-6","volume":"24","author":"L Torjai","year":"2016","unstructured":"Torjai, L., Kruzslicz, F.: Mixed integer programming formulations for the biomass truck scheduling problem. CEJOR 24(3), 731\u2013745 (2016)","journal-title":"CEJOR"},{"issue":"10","key":"1925_CR36","doi-asserted-by":"publisher","first-page":"2109","DOI":"10.1134\/S0005117910100103","volume":"71","author":"F Werner","year":"2010","unstructured":"Werner, F., Kravchenko, S.A.: Scheduling with multiple servers. Autom. Remote Control 71(10), 2109\u20132121 (2010)","journal-title":"Autom. Remote Control"},{"key":"1925_CR37","doi-asserted-by":"crossref","unstructured":"Xie, X., Li, Y., Zhou, H., Zheng, Y.: Scheduling parallel machines with a single server. In: Proceedings of 2012 International Conference on Measurement, Information and Control, vol.\u00a01, pp. 453\u2013456. IEEE (2012)","DOI":"10.1109\/MIC.2012.6273340"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01925-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01925-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01925-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T11:05:00Z","timestamp":1698663900000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01925-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":37,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1925"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01925-2","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,10]]},"assertion":[{"value":"14 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}