An edge coloring of a graph is a function that assigns a color to each edge such that whenever and have a common endpoint. Denoting the set of colors assigned to the edges incident to a vertex , and the minimum number of integers which must be added to to form an interval, the deficiency of an edge coloring is defined as the sum , and the span of is the number of colors used in . The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.