The　rapid　growth　of　cloud　computing　has　brought　new　challenges　in　Parallel　Batch　Machine　Scheduling　(PBMS),　particularly　when　incorporating　malleability　and　rejection　constraints.　This　has　led　to　the　Parallel　Batch　Machine　Scheduling　with　Malleability　and　Rejection　problem　(PBMSMR),　which　involves　malleable　jobs　whose　widths　can　be　adjusted　during　execution　within　specified　limits　and　incorporates　job　rejection　subject　to　a　penalty　threshold.　Based　on　an　analysis　of　key　properties　of　batch　scheduling　with　job　rejection,　we　develop　an　approximation　algorithm　for　PBMSMR　by　employing　a　greedy　approach　that　reorders　and　iteratively　refines　job　sets　to　minimize　the　objective　while　respecting　rejection　constraints.　The　algorithm　achieves　a　time　complexity　of　O(n2logn)　and　an　approximation　ratio　of　(4-2Km),　where　K　and　m　denote　the　capacities　and　the　number　of　the　machines,　respectively.　For　jobs　with　identical　release　times,　we　fine-tune　the　algorithm　to　achieve　an　approximation　ratio　of　(3+2(K-1)Km).　Additionally,　for　PBMS　with　two　machines　of　non-identical　capacities　and　fixed-width　jobs,　we　achieve　a　ratio　of　175　with　O(nlogn),　improving　upon　the　previous　state-of-the-art　approximation　ratio　of　5　with　a　runtime　of　O(n2).　©　The　Author(s),　under　exclusive　license　to　Springer　Nature　Singapore　Pte　Ltd.　2025.