Exact and approximation algorithms for a scheduling problem
Exact and approximation algorithms for a scheduling problemStanford University. Systems Optimization Laboratory
Sign up to use
Exact and approximation algorithms for a scheduling problem

Exact and approximation algorithms for a scheduling problem

Sign up to use
Sign up to use
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*