An efficient algorithm to solve 1// ∑Ci+∑Yi problem

Abstract

In the problem of scheduling a single machine to minimize the sum of completion time and total late work, there are n jobs to be processed for which each has an integer processing time and a due date. The objective is to minimize the sum of total completion time and total late work ,where the late work for a job is the amount of processing of this job that is performed after its due date. Although dominance rules are derived for the special cases in which all processing times are equal and all due dates are equal. Algorithm H is presented for the general non preemptive sum of completion time and the total late work simultaneous problems