Abstract: Recent advancements in cloud computing serves as a solution for many real world problems and one best application is the streaming system. Customizing, accessing and sharing of the multimedia files which are procured in the cloud is not alone streaming. Technically there are many other issues that have to be concentrated while streaming live contents. High-definition video applications are often challenging for mobile devices due to their limited processing capability and bandwidth-constrained network connection. The proliferation of cloud based educational system has raised the requirements for efficient representation of video where previously standardized video coding technology can hardly keep pace. Especially in live streaming, transcoding needs to be carried out on the fly with acceptable speed to maintain better quality of service. The objective of this paper is to propose a cloud based transcoding system using MapReduce to perform parallel operations, balancing the load of VM’s. The study concentrates on NP-hard problem which aggregates job assignment overhead and scheduling based on capacity of the machines. There are two contributions proposed in this study, first is an algorithm to rule out redundancies in similar frames. A highly efficient algorithm called Extended Mode Prediction for Transcoding (EMPT) is proposed which takes care of the transcoding part. The second is a novel low complexity heuristic algorithm called Optimal Reduced Finish Time (ORFT) to minimize the overall finish time taken for transcoding. By considering the average complete time as the lower bound, an optimal solution is framed for the above mentioned problem. Implementation has been carried out using mathematical simulations and analysis to prove that the proposed algorithm outperforms better than the existing algorithms with a low complexity of O (nlogn).