Downloads & Free Reading Options - Results

This paper discusses problems that arose in calendaring cases for an appellate court. The first problem is to distribute cases among panels of judges so as to equalize work loads. We give a worst case analysis of a heuristic for this NP-complete problem. For a given distribution denote by z the heaviest work load. We wish to minimize z. The ratio of the heuristic value z-bar to that of the true optimum z* is shown to be z-bar/z* or = (k + 3)/(k + 2) where all the case weights in (0, (1/k)z*), generalizing a result of Graham on multiprocessor scheduling. Under a restrictive assumption on the case weights, some generalizations of this scheduling problem are solved. Characterizations for feasible calendars and polynomial algorithms for finding these feasible solutions are given. Algorithms are given for choosing an optimal subset of the backlogged cases that can be calendared. (Author)