Exact and Heuristic Algorithms for the Jump Number Problem

Given a partially ordered set P=(V,<_P) (also called partial order or poset) a linear extension L=(V,<_L) of P is a total order on the same ground set V of P, such that each couple of element u, v of V for which u <_P v implies u <_L v. Given two consecutive elements u, v of L the couple (u, v) forms a jump or setup if u, v are not comparable in P. The jump number problem of P consists in determining a linear extension L of P with minimum number of jumps. It arises, for example, from scheduling problems where n tasks, subject to precedence constraints given by a partial ordering, are to be processed on a single processor, where a processor setup unit cost is occurred when the processor switches from one task to another which is not constrained to precede it; the problem consists in finding a schedule with minimum setup number. We present an exact algorithm based on dynamic programming and a heuristic algorithm for the jump number problem for general posets. The algorithms have been experimentally evaluated on a set of randomly generated posets of different size and different density. Concerning the heuristic algorithm we have seen that it has produced optimal solutions for a large set of test problems and in the worst case the relative error was not greater than 0.2. Regarding the dynamic programming algorithm the number of states generated and the time spent by it are strictly related to the relative gap (UB - LB)/LB.