Thursday, January 21, 2010

Linear Ordering Problems

Linear Ordering Problems (LOP) are encountered in a wide range of applications, such as ranking sports teams, triangulation of matrices (i.e., finding a reordering of the rows and columns that maximizes the total above or below the diagonal), or ordering lists of individual preferences. Recently I came across an interesting application for the scheduling of printing tasks. The data consisted of a array of entries $x_{ij}$  which give the time saved if task i is completed before task j.  The times savings were attributed to setup work done for the first task that would benefit subsequent tasks.  The problem was to find an ordering of tasks that maximize the overall time savings.

Like many problems in Operations Research, the LOP has a rich history of study and algorithm development.  LOP are  known to be NP hard, but state of the art algorithms provide for many practical uses. A somewhat older MILP formulation is easily implemented in GMPL/GLPK as shown in the Scheduling: Linear Ordering of Tasks example.

No comments:

Post a Comment