A Machine-Job Scheduling Model

This paper makes use of a device proposed by Fulkerson and Ford for maximal multi-commodity network flows (Ford, L. R. Jr., D. R. Fulkerson. 1958. A suggested computation for maximal multi-commodity network flows. The RAND Corporation, Paper P-1114, March 27, 1958. Also Management Sci. 5(1) 97–101.). A machine-job scheduling model is formulated that avoids the usual in-process inventories and thereby has fewer equations. The activities are the possible sequence for each job of machine steps and interspersed delays; this, of course, greatly multiplies the number of activities. However, a compact network representation of the set of possible activities is developed which permits generating just the activity to enter the basis on each iteration without explicitly generating the others. This is done by using one of the efficient procedures that now exist for computing the shortest route through a network (Dantzig, George B. 1960. On the shortest route through a network. Management Sci. 6(2); Moore, E. F. The shortest path through a maze. Unpublished mimeographed report, 16 pages; Bellman, Richard. 1958. On a routing problem. JORSA, XVI(1) 87–90.), (Ford, L. R. Jr. 1956. Network flow theory. The RAND Corporation, Paper P-923).

• 저널Management Science · 6(2) · 191–196
• 토픽Scheduling and Optimization Algorithms · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.6.2.191
• 저자George B. Dantzig