This　paper　investigates　a　new　bi-objective　parallel　machine　scheduling　and　location　problem:　selecting　locations　for　available　machines,　assigning　jobs　to　these　located　machines　for　processing,　and　sequencing　the　assigned　jobs　on　each　machine　to　optimize　the　location　cost　and　makespan,　simultaneously.　For　the　challenging　NP-hard　problem,　we　first　develop　a　novel　bi-objective　mixed-integer　linear　programming　(MILP)　model　with　fewer　integer　variables　compared　with　the　state-of-the-art　one.　Then,　several　valid　inequalities　are　proposed　to　tighten　it　further.　We　develop　an　ɛ-constraint　based　on　the　fuzzy-logic　method　to　solve　the　bi-objective　model.　Computational　results　for　benchmark　instances　show　that　the　proposed　approach　obtains　more　Pareto-optimal　solutions　compared　with　the　state-of-the-art　one　and　is　more　than　15　times　faster　than　it.　Valid　inequalities　can　reduce　average　computation　time　by　more　than　90%.　©　2022　Elsevier　Ltd