  In this paper we deal with the Bin Packing Problem with Conflicts on interval
graphs: given an interval graph, a nonnegative integer weight for each vertex,
and a nonnegative integer B, find a partition of the vertex set of the graph
into k subsets such that the sum of the weights of the vertices assigned to
same subset is less than or equal to B, two vertices connected by an edge do
not belong to the same subset, and k is minimum. We design a heuristic
algorithm, and propose a new random interval graph generator which builds
interval conflict graphs with desired edge density. We test the algorithm on a
huge test bed, and compare the results with existing algorithms.
