Precedence Constraint Scheduling and Connections to Dimension Theory of Partial Orders

Abstract

In this paper we survey recent results on the precedence constraint single machine scheduling problem to minimize the weighted sum of completion times. We show how we can benefit from known results in dimension theory of partial orders to obtain improved approximate solutions when precedence constraints have low fractional dimension. We believe that dimension theory of partial orders could be of interest for other linear ordering problems as well. 1