Worst-case analysis of heuristics for the local microcode optimization problem

Abstract.  The local microcode optimization problem is a superposition of a multiprocessor scheduling and a coloring problem. For its solution, many heuristics have already been proposed, but no investigations of their worst-case behavior have become known as yet. We show for some of them, that their worst-case performance ratio is infinite although they use powerful procedures to solve NP-complete subproblems exactly.