Example 6.13 Machine Loading Problem

Machine loading problems arise in a variety of applications. Consider a simple instance as described in Ahuja, Magnanti, and Orlin (1993). Assume you need to schedule the production of three products, – , on four machines, – . Suppose that machine 1 and machine 2 are each available for 40 hours and machine 3 and machine 4 are each available for 50 hours. Also, any of the machines can produce any product. The per-unit processing time and production cost for each product on each machine are indicated in Table 6.9.

The problem is to satisfy the demands for the three products at minimum cost.

You can model this problem as a generalized network as shown in Output 6.13.1. The network has three product nodes with demands indicated by positive supdem values and four machine nodes with availabilities (in hours) indicated by negative supdem values. The multiplier on an arc between a machine and a product indicates the hours of machine capacity needed to produce one unit of the product.

Output 6.13.1 Machine Loading Problem

You can create the input data sets with the following SAS code:

data mlarcs;
   input _from_ $ _to_ $ _cost_ _mult_;
datalines;
P1  M1   4   .
P1  M2   3   2
P1  M3   3   2
P1  M4   1   3
P2  M1  .5   2
P2  M2   2   3
P2  M3  .5   2
P2  M4   3   1
P3  M1   2   3
P3  M2   5   .
P3  M3   1   2
P3  M4  .5   4
;

data mlnodes;
   input _node_ $ _sd_;
datalines;
P1   10
P2   5
P3   10
M1  -40
M2  -40
M3  -50
M4  -50
;

You can solve the problem using the following call to PROC NETFLOW:

title1 'The NETFLOW Procedure';
proc netflow 
   excess   = demand
   arcdata  = mlarcs      
   nodedata = mlnodes
   conout   = mlsol;
run;

The optimal solution, as displayed in Output 6.13.2, can be interpreted as follows:

• Product 1: 10 units on machine 4

• Product 2: 3 units on machine 1, and 2 units on machine 3

• Product 3: 5 units on machine 3, and 5 units on machine 4