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 7.9.
Table 7.9: Processing Times and Production Costs
M1 |
M2 |
M3 |
M4 |
|
P1 |
1 |
2 |
2 |
3 |
P2 |
2 |
3 |
2 |
1 |
P3 |
3 |
1 |
2 |
4 |
M1 |
M2 |
M3 |
M4 |
|
P1 |
4 |
3 |
3 |
1 |
P2 |
0.5 |
2 |
0.5 |
3 |
P3 |
2 |
5 |
1 |
5 |
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 7.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 7.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 7.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
Output 7.13.2: Optimum Solution to the Machine Loading Problem
The NETFLOW Procedure |
Obs | _from_ | _to_ | _cost_ | _CAPAC_ | _LO_ | _mult_ | _SUPPLY_ | _DEMAND_ | _FLOW_ | _FCOST_ |
---|---|---|---|---|---|---|---|---|---|---|
1 | P1 | M1 | 4.0 | 99999999 | 0 | 1 | 10 | 40 | 0.00000 | 0.00000 |
2 | P2 | M1 | 0.5 | 99999999 | 0 | 2 | 5 | 40 | 3.67856 | 1.83928 |
3 | P3 | M1 | 2.0 | 99999999 | 0 | 3 | 10 | 40 | 0.00000 | 0.00000 |
4 | P1 | M2 | 3.0 | 99999999 | 0 | 2 | 10 | 40 | 0.00000 | 0.00000 |
5 | P2 | M2 | 2.0 | 99999999 | 0 | 3 | 5 | 40 | 0.00000 | 0.00000 |
6 | P3 | M2 | 5.0 | 99999999 | 0 | 1 | 10 | 40 | 0.00000 | 0.00000 |
7 | P1 | M3 | 3.0 | 99999999 | 0 | 2 | 10 | 50 | 0.00000 | 0.00000 |
8 | P2 | M3 | 0.5 | 99999999 | 0 | 2 | 5 | 50 | 1.32144 | 0.66072 |
9 | P3 | M3 | 1.0 | 99999999 | 0 | 2 | 10 | 50 | 5.00000 | 5.00000 |
10 | P1 | M4 | 1.0 | 99999999 | 0 | 3 | 10 | 50 | 10.0000 | 10.0000 |
11 | P2 | M4 | 3.0 | 99999999 | 0 | 1 | 5 | 50 | 0.00000 | 0.00000 |
12 | P3 | M4 | 0.5 | 99999999 | 0 | 4 | 10 | 50 | 5.00000 | 2.50000 |