Scheduling to Minimize Maximum Workload

We pose the following problem: given m jobs, each of which requires a certain total amount of labour that must be performed within specified time periods, how should one schedule the jobs' execution to obtain a total workload that is as even as possible? A related question is: what is the minimal work capacity needed to accomplish all jobs? These questions can be formulated as a linear program, but the number of variables and constraints required usually will be large. Using linear duality theory we instead derive a purely combinatorial problem whose resolution leads to the needed minimal capacity, and thus to the imposed bottleneck. Then we concentrate on the important special case where the time constraints for performing each job are in the form of a single time interval: We detail a simple procedure that efficiently determines the minimal capacity and the bottleneck. A second efficient combinatorial algorithm determines a feasible execution schedule which minimizes the maximum total workload. These algorithms require a computational time of the order of m² and negligible core memory, and for most practical applications can be implemented on microcomputers.