Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
研究在同类并行机上调度n个作业的问题，每个作业有处理时间、释放时间和截止日期。通过构造网络最大流来判定可行调度，并给出最大延迟准则的优化算法，复杂度优于此前方法。
We consider the problem of scheduling n jobs, each with a specific processing requirement, release time and due date on m uniform parallel machines. It is shown that a feasible schedule can be obtained by determining the maximum flow in a network, thus permitting the use of standard network flow codes. Using a specialized maximum flow procedure, the complexity reduces to O(tn 3 ) operations when t is the number of distinct machine types. Previous algorithms solve the feasibility problem in O((m + log n)(m 2 n 3 + n 4 )) operations. In addition to the feasibility problem, we describe algorithms for the maximum lateness criterion. Here we develop a bound which compares even more favorably to the best previous bound. We also show how other criteria with respect to the amount of work completed on each job prior to its due date or the amount of work scheduled in each of a sequence of periods can be optimized by similar path augmenting techniques.