This　paper　studies　a　new　large-scale　emergency　medical　services　scheduling　(EMSS)　problem　during　the　outbreak　of　epidemics　like　COVID-19,　which　aims　to　determine　an　optimal　scheduling　scheme　of　emergency　medical　services　to　minimize　the　completion　time　of　nucleic　acid　testing　to　achieve　rapid　epidemic　interruption.　We　first　analyze　the　impact　of　the　epidemic　spread　and　assign　different　priorities　to　different　emergency　medical　services　demand　points　according　to　the　degree　of　urgency.　Then,　we　formulate　the　EMSS　as　a　mixed-integer　linear　program　(MILP)　model　and　analyze　its　complexity.　Given　the　NP-hardness　of　the　problem,　we　develop　two　fast　and　effective　improved　discrete　artificial　bee　colony　algorithms　(IDABC)　based　on　problem　properties.　Experimental　results　for　a　real　case　and　practical-sized　instances　with　up　to　100　demand　points　demonstrate　that　the　IDABC　significantly　outperforms　MILP　solver　CPLEX　and　two　state-of-the-art　metaheuristic　algorithms　in　both　solution　quality　and　computational　efficiency.　In　addition,　we　also　propose　some　managerial　implications　to　support　emergency　management　decision-making.　©　2023,　The　Author(s),　under　exclusive　licence　to　Springer　Science+Business　Media,　LLC,　part　of　Springer　Nature.