An efficient job scheduling algorithm for mixed turnaround and deadline applications

Abstract

Computer job scheduling is often performed with little understanding of the formal properties of the jobs being scheduled. One reason for this is that optimal solutions for job scheduling on computers are difficult to obtain if the job stream has mixed objectives, i.e., it consists of some jobs whose turnaround time has to be minimized and others whose deadlines must be met. A practical algorithm for scheduling mixed job streams on monoprogrammed computers, with potential application to a multiprogramming environment, is presented. The algorithm takes into account variable cost rates for each job. Experimental results illustrate the efficiency of the algorithm in terms of both its proximity to optimal solutions and its low computational complexity.