An Improved Algorithm for Scheduling Jobs on Identical Machines

The problem discussed in this paper is one in which n jobs are to be scheduled on M identical machines. Each job, i, possesses a processing time, ti , a linear penalty rate, pi, and a due date, di = ti -for all i. The objective is to minimize the total penalty cost, where Ti is the actual completion time for job i. The improved algorithm is based upon the technique of Elmaghraby and Park and is the result of three theoretical refinements of their basic method in conjunction with newly developed results. A detailed discussion of the refinements and new results is followed by a presentation of some representative computational results using the improved algorithm.