The　scheduling-location　(ScheLoc)　problem　is　a　new　and　interesting　field,　which　is　a　combination　of　two　complex　problems:　the　machine-location　problem　and　the　scheduling　problem.　Owing　to　the　NP-hardness　of　both　the　component　problems,　the　ScheLoc　problem　is　naturally　NP-hard.　This　study　investigates　a　deterministic　and　discrete　parallel-machine　ScheLoc　problem　for　minimizing　the　makespan.　A　new　mixed　integer　programming　formulation　based　on　network　flow　problems　is　proposed.　Two　formulation-based　heuristics　are　developed　for　small-scale　problems.　Subsequently,　a　polynomial-time　heuristic　is　designed　for　efficiently　solving　large-scale　problems.　Extensive　computational　experiments　are　conducted　for　1450　benchmark　problem　instances　with　different　scales.　The　computational　results　show　that　our　model　can　solve　more　problem　instances　to　optimality　than　that　in　Heßler　and　Deghdak　(2017)　in　the　same　time　limit.　In　addition,　the　heuristics　can　yield　near-optimal　solutions　for　small-scale　problems　in　a　short　time.　The　polynomial-time　algorithm　outperforms　most　of　the　state-of-the-art　methods　for　the　large-scale　problems　in　terms　of　both　the　efficiency　and　solution　quality.　©　2019　Elsevier　Ltd