Scheduling to Minimize Maximum Workload
研究如何调度m个任务使得总工作负荷尽可能均匀，并利用线性对偶理论转化为组合问题，针对任务时间约束为单区间的情形给出高效算法，适用于微计算机实现。
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 2 and negligible core memory, and for most practical applications can be implemented on microcomputers.