• EXACT ALGORITHM FOR MINIMIZING THE SUM OF TOTAL TARDINESS AND TOTAL LATE WORK PROBLEM

Abstract

This paper presents a branch and bound (BAB) algorithm for minimizing the sum of total tardiness and total late work within the single machine problem. Late work for job i is the amount of processing performed on i after its due date    d­_i. Branch and bound (BAB) is proposed. This BAB proposes two lower bounds one is based on the decomposition property of the bi-criteria problem the other one based on relaxation of objective .and two dominance rules with special cases. Based on results of computational experiments, conclusions are formulated on the efficiency of the BAB algorithm.