Minimizing setups in precedence constrained scheduling

In this dissertation, we investigate the problem of minimizing the setup cost in precedence constrained scheduling. When the cost of all setups is the same, this problem is equivalent to finding a linear extension of a partial order with minimum number of jumps. This problem is well known as the jump number problem. For general partial orders, the jump number problem was shown to be NP-hard by Pulleyblank in 1981. We show that the problem is polynomial for two restricted classes of partial orders; interval orders and 2-dimensional lattices. Algorithms for finding the optimal linear extensions for these classes are developed and analyzed. Finally, we consider the jump number problem for the class of 2-dimensional orders. A dimension preserving transformation from 2-dimensional orders to 2-dimensional lattices is developed. This transformation leads to an optimal algorithm for solving the jump number problem for 2-dimensional orders. We also study the relationships among all classes of partial orders for which the jump number problem is known to be polynomial and characterize the class of posets that contains all these classes