In this paper, we develop a batching algorithm to provide Video on Demand (VoD) streaming service over wireless networks considering heterogeneous characteristics of VoD service. The proposed batching service considers both reneging behavior and adaptive modulation and coding (AMC). Two reneging behavior models are considered: the exponential and the convex models. A nonlinear programming problem is suggested for each reneging model to minimize the service latency with the reneging probability and the network capacity constraints. The performance of the reneging and AMC based network capacity of the proposed batching algorithm is experimented and compared to the unicast procedures. Simulations are performed to illustrate the excellence of the proposed batching algorithm. The AMC based network capacity and exponential reneging improve the latency by 66-77 and 35-46% respectively for high service arrival rates.