A Branch and Bound procedure to minimize Mean Absolute Lateness on a single processor

This paper presents a solution procedure to minimize the Mean Absolute Lateness single machine scheduling problem. A Branch and Bound methodology is utilized in conjunction with a one-pass linear program to find an optimal solution. In order to fathom branches, several theorems are developed to establish dominance between adjacent job pairs and in some cases between three adjacent jobs. In addition, several theorems are presented to establish lower bounds on the solution to further limit the enumeration. A simple decomposition procedure is shown to reduce problem size in many cases. Solution results indicate that problem characteristics, in addition to size, have a major impact on solution requirements. As the tightness of due dates increases, a corresponding increase in solution requirements is evident. For example, for problems of size N=25, the solution requirements when tightness was 0.1 is an average 0.035 CPU seconds while 3234.0 CPU seconds were required to solve problems with a tightness of 0.9. Conversely, as the due date coefficient of variation (CV) increases, solution requirements lessen. For problems of size N=20 and a CV of 0.2, CPU time required to find an optimal solution was 16.8 compared to 0.01 seconds for a CV of 0.6. Solution times for certain problems up to N=30 were reported.