A DEADLINE AWARE APPROXIMATION ALGORITHM FOR SCHEDULING JOBS WITH BURST TIME AND PRIORITIES

Abstract

System’s performance is highly affected by CPU Scheduling. Effective scheduling leads to better system performance. Process scheduling problem is a combinatorial problem in which arrangement of jobs is a key factor. Different algorithms and techniques have been developed, used to find the above factor, many techniques such as FCFS, SJF, Round- Robin, Priority, Multi-Level Queue and many more are applied but all these technique provide sequence of job relevant to their properties, the sequence which is necessary toward our requirement may be not full-filled by applying previously known techniques, to find such sequence its take exponential time. In this project we proposed a method for process scheduling using a deadline aware approximation algorithm to provide efficient process scheduling, where required schedule has a certain weightage of priority and Burst time of job. In our problem we solve the desire sequence of jobs by using four approximation techniques. To solve above problem in polynomial time there are approximation algorithms which solve the sequence of jobs in polynomial time. Genetic algorithm (GA) is one such approximation technique and another one is Artificial-Bee-Colony (ABC). Two further techniques are the modified-GA and modified-ABC. In real life problems we have a deadline to complete certain set of jobs, we have to decide the sequence of job in which we complete our jobs before or nearby deadline, our proposed technique provide a way which leads toward a good solution, we known each job take some duration to execute (i.e. Burst time) and each job is associate with some priority, so considering both factor we developed a method in which we provide a certain weightage (requirement percentage) to priority, this lead to total completion time of jobs ( Total-Turn- Around time) . Toward Total-Turn-Around time (TAT) we find a sequence of jobs. We apply approximation algorithms to find desire schedule, our proposed CPU Scheduling method and comparison is made on the performance of CPU scheduling with and without the proposed technique in terms of number of iteration, number of test case, requirement percentage and tardiness (fitness value).