This　paper　addresses　the　problem　of　minimizing　the　maximum　lateness　and　the　total　pollution　emission　costs　by　scheduling　a　group　of　jobs　with　different　processing　times,　sizes,　release　times,　and　due　dates　on　uniform　parallel　batch　processing　machines　with　non-identical　machine　capacities　and　different　unit　pollution　emission　costs.　We　develop　a　discrete　bi-objective　evolutionary　algorithm　C-NSGA-A　to　solve　this　problem.　On　the　one　hand,　we　present　a　method　of　constructively　generating　an　individual　with　the　first　job　selection　to　produce　an　initial　population　for　improving　the　convergence　of　individuals.　On　the　other　hand,　we　propose　an　angle-based　environmental　selection　strategy　to　choose　individuals　to　maintain　the　diversity　of　individuals.　Through　extensive　simulation　experiments,　C-NSGA-A　is　compared　with　several　state-of-the-art　algorithms,　and　experimental　results　show　that　the　proposed　algorithm　performs　better　than　those　algorithms.　Moreover,　the　proposed　algorithm　has　more　obvious　advantages　on　instances　with　a　larger　number　of　jobs.　©　2022　Elsevier　Ltd