Exact algorithm for minimizing the sum of total late work and maximum late work problem

Abstract

This paper presents a branch and bound (BAB) algorithm for minimizing the sum of total late work and maximum late work problem within the single machine context. Late work is the amount of work executed after a given due date. Branch and bound (BAB) is proposed, two heuristic methods are used to find an upper bound. This BAB proposes a lower bound based on the decomposition property of the bi-criteria problem. Based on results of computational experiments, conclusions are formulated on the efficiency of the BAB algorithm.