Full 4K videos (3840x2160, 60 FPS) are becoming popular in human life. They can provide better user experience because of their sharpness and smoothness. However, the lack of full 4K video sources is limiting their popularization. The problem can be overcome by up converting HD (1920x1080, 24 FPS) videos, but the transcoding progress is time consuming, and traditional distributed video transcoding is not applicable as frame rate up convert (FRUC) during the progress may introduce timestamp mismatch and quality loss. What’s more, cases like IPTV need video streams with a fixed group of pictures (GOP) to obtain stable transmitting and channel switching, while no existing distributed transcoding method can obtain such requirement. To utilize the advantages of cloud computing in such scenarios, in this paper we propose a novel distributed scheduling algorithm for FRUC video transcoding.The algorithm slice videos at instantaneous decoder refresh (IDR) frames to prevent quality loss, and introduce overlap while processing for fixing GOP, and finally remove the redundancies for timestamp matching. Experiment results show that with the same amount of computing resources, our algorithm transcodes a video faster than single node transcoder, and shows more efficiency than single node transcoder when the number of CPU cores increases.