An Improved Heuristic for Minimizing Total Completion Time on Single Machine with Release Time

Abstract: This study considers the scheduling problem of minimizing the total completion time on a single machine with release dates. In view of the NP-Hard nature of the problem, one heuristic (called MM) was proposed for this problem. The proposed heuristic and two others (AEO and HR1) selected from the literature were tested on a total of 450 randomly generated single machine scheduling problems ranging from 3 to 500 jobs. Experimental results show that the proposed heuristic outperforms the AEO algorithm with respect to effectiveness and efficiency. Also, the proposed heuristic outperforms the HR1 heuristic with respect to effectiveness