Techniques of Finding Lower Bounds in Multi Objective Functions

In this paper, the problm of sequencing n jobs on one machine is considered with a multi objective function.Two problems have been studied, sum of completion times added with the maximum tardiness i i T c max ) and sum of completion times with the maximum tardiness ( ∑ ∈N i i T and c max ), the first one has optimal solution solved by Branch and bound technique, the second has efficient solutions founded by Van Wassenhove algorithm.A theorem is presented to show a relation between the number of efficient solutions, lower bound (LB) and optimal solution.This theorem restricts the range of the lower bound, which is the main factor to find the optimal solution.Also the theorem opens algebraic operations and concepts to find new lower bounds.