In this paper, we have investigated the video pre-processing and the VCR operations for the Video on Demand (VoD) system. We have proposed a novel technique for the segmentation of the movies using Markov Chain Monte Carlo (MCMC). Our proposed segmentation technique will segment the videos by identifying the scene boundary locations. The objective of this paper is to reduce the accessing time for the new requests of the movies using M-chaining technique and also to reduce the seeking time for the VCR operations using our segmentation technique. We have numerically analysed the existing segmentation techniques with our proposed segmentation technique. We found that our segmentation technique shows the less computational time compared with other segmentation techniques. The performance of the segmentation techniques is measured in terms of Precision as well as Recall and our technique gives more accurate results compared with other segmentation techniques. The VCR functionalities are simulated by applying our segmentation technique and the results of the simulation show less accessing and seeking time. We have also addressed the practical issues of efficient utilisation of overall bandwidth and buffer of the VoD system using our segmentation technique.