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(tn3) operations when t is the number of distinct machine types. Previous algorithms solve the feasibility problem in O((m + log n)(m2n3 + n4)) 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.
Federgruen, Awi, and Henri Groenevelt. "Preemptive scheduling of uniform machines by ordinary network flow techniques." Management Science 32, no. 3 (March 1986): 341-349.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.