On a special scheduling problem of posets

الملخص EN

Given a finite ordered set p.

Find a linear extension of p which preserves a minimum number of covering relations of p.

This article mainly concentrates on this problem, called the bump number problem.

In particular we present some new results concerning the “greedy” ordered sets; these are the ordered sets for which the “greedy algorithm” always produces an optimal solution.