In the computational grid we need effective schedulers to minimize the makespan that are spent for the execution of the jobs. Conventional scheduling algorithms do not concern over quality of service. In this work, a job scheduling heuristic based on quality of service is proposed and a simulation application is developed by using GridSim toolkit to investigate the performance of the heuristic. The experiments demonstrate the effectiveness of the improved Min-Min heuristic in terms of jobs' special requirements. Our experimental results indicate that the novel strategy can reduce the completion time of jobs with constraints and improve user satisfaction.