Klaus Reuter
Universidade de Hamburgo
Resumo: Let us assume that a machine performs a set of jobs one at a time subject to a set of precedence constraints. We consider the problem of scheduling the jobs to minimize the number of setups. This problem leads to a well studied parameter of an ordered set P, the so-called jump number of P. Besides a report on several known results we shall present a surprising relationship to the length of the lattice of maximal antichains of P. This allows us in some cases to solve the jump number problem in polynomial time. In addition, we shall explain how the jump number problem of levels of Boolean lattices is related to an extremal set problem which can be solved by a method of Lovasz.