Trailing-Edge
-
PDP-10 Archives
-
decuslib20-01
-
decus/20-0020/assign.tuk
There are 2 other files named assign.tuk in the archive. Click here to see a list.
10' NAME--ASSIGNMT
20'
30' DESCRIPTION
32 REM THIS PROGRAM USES THE GILMORE ALGORITHM DESCRIBED IN THE
34 REM COMMUNICATIONS OF THE ACM(NOV.1960,PP.605-606) TO SOLVE
36 REM THE CLASSIC ASSIGNMENT PROBLEM AND COMPUTE A COST FOR THE
38 REM ASSIGNMENT.
40'
50' SOURCE--UNKNOWN
60'
70' INSTRUCTIONS
72 REM DATA IS ENTERED STARTING LINE 2000 IN THE FOLLOWING FORMAT:
74 REM
76 REM 1) FIRST ENTER N, THE NUMBER OF MODULES TO BE ASSIGNED
78 REM N.B. IT IS ASSUMED THAT THERE ARE ALSO N LOCATIONS.
80 REM
82 REM 2) NEXT ENTER E(I,J), THE 'RATING MATRIX'
84 REM N.B. E(I,J) IS CONSIDERED TOBE (MODULES,LOCATIONS)
85'
87' THIS PROGRAM WAS WRITTEN FOR STUDENT USE AT AMOS TUCK SCHOOL
88' OF HANOVER, N.H. WHICH DOES NOT ASSUME RESPONSIBILITY FOR ITS
89' ACCURACY.
90'
95' * * * * * * * * * * * * MAIN PROGRAM * * * * * * * * * * * *
97'
100 DIM E(50,50),R(50),X(50),Y(50),M(50),L(50),F(50),G(50)
140 REM INITIALIZE
150 READ N
160 FOR I=1TO N
170 FOR J=1TO N
180 READ E(I,J)
190 NEXT J
200 NEXT I
210 LET T=0
220 FOR I=1 TO N
230 LET X1=E(I,1)
240 FOR J=2 TO N
250 IF E(I,J)>=X1 THEN 270
260 LET X1=E(I,J)
270 NEXT J
280 FOR J=1TO N
290 LET E(I,J)=E(I,J)-X1
300 NEXT J
310 LET T=T+X1
320 NEXT I
330 FOR J=1TON
340 LET X1=E(1,J)
350 FOR I=2 TO N
360 IF E(I,J)>=X1 THEN 380
370 LET X1=E(I,J)
380 NEXT I
390 FOR I=1TO N
400 LET E(I,J)=E(I,J)-X1
410 NEXT I
420 LET T=T+X1
430 NEXT J
440 FOR I=1TO N
450 LET X(I)=Y(I)=0
460 NEXT I
470 FOR I=1 TO N
480 FOR J=1 TO N
490 IF E(I,J)<>0 THEN 540
500 IF X(I)<>0 THEN 540
510 IF Y(J)<>0 THEN 540
520 LET X(I)=J
530 LET Y(J)=I
540 NEXT J
550 NEXT I
560 REM SILVER START START LABELING
570 LET F1=N
580 LET R1=C1=0
600 LET R2=1
610 FOR I=1 TO N
620 LET M(I)=L(I)=0
640 IF X(I)<>0 THEN 690
650 LET R1=R1+1
660 LET R(R1)=I
670 LET M(I)=-1
680 LET F1=F1-1
690 NEXT I
700 IF F1=N THEN 1420
710 REM LABEL LABEL AND SCAN
720 LET I=R(R2)
730 LET R2=R2+1
740 FOR J=1 TO N
750 IF E(I,J)<>0 THEN 840
760 IF L(J)<>0 THEN 840
770 LET L(J)=I
780 LET C1=C1+1
790 LET F(C1)=J
800 IF Y(J) =0 THEN 1320
810 LET R1=R1+1
820 LET R(R1)=Y(J)
830 LET M(Y(J))=I
840 NEXT J
850 IF R2<=R1 THEN 710
860 REM RENORMALIZE
870 LET S1=1
880 LET C0=C1
890 LET C2=0
900 FOR J=1 TO N
910 IF L(J)<>0 THEN 940
920 LET C2=C2+1
930 LET G(C2)=J
940 NEXT J
950 LET X1=E(R(1),G(1))
960 FOR K=1 TO R1
970 FOR L1=1 TO C2
980 IF E(R(K),G(L1))>X1 THEN 1000
990 LET X1=E(R(K),G(L1))
1000 NEXT L1
1010 NEXT K
1020 LET T=T+(R1+C2-N)*X1
1030 FOR I=1 TO N
1040 IF M(I)<>0 THEN 1090
1050 FOR L1=1 TO C0
1060 LET E(I,F(L1))=E(I,F(L1))+X1
1070 NEXT L1
1080 GOTO 1240
1090 FOR L1=1 TO C2
1100 LET E(I,G(L1))=E(I,G(L1))-X1
1110 ON S1 GOTO 1120,1230,1270,1320
1120 IF E(I,G(L1)) <> 0 THEN 1230
1130 IF L(G(L1))<>0 THEN 1230
1140 LET L(G(L1))=I
1150 IF Y(G(L1)) <> 0 THEN 1190
1160 LET J=G(L1)
1170 LET S1=2
1180 GOTO 1230
1190 LET C1=C1+1
1200 LET F(C1)=G(L1)
1210 LET R1=R1+1
1220 LET R(R1)=Y(G(L1))
1230 NEXT L1
1240 NEXT I
1260 ON S1+2 GOTO 1120,1230,1270,1320
1270 IF C0=C1 THEN 710
1280 FOR I=C0+1 TO C1
1290 LET M(Y(F(I)))=F(I)
1300 NEXT I
1310 GOTO 710
1320 REM MARK MARK NEW COLUMN AND PERMUTE
1330 LET Y(J)=I=L(J)
1350 IF X(I) <>0 THEN 1380
1360 LET X(I)=J
1370 GOTO 570
1380 LET K=J
1390 LET J=X(I)
1400 LET X(I)=K
1410 GOTO 1330
1420 REM CONTINUE
1430 FOR I=1 TO N
1440 FOR J=1 TO N
1450 LET E(I,J)=0
1460 NEXT J
1470 NEXT I
1480 FOR K=1 TO N
1490 LET E(Y(K),X(Y(K)))=1
1500 NEXT K
1510 PRINT
1520 PRINT
1530 PRINT" ","THE ASSIGNMENT IS"
1540 PRINT
1550 PRINT"MODULE\LOCATION"
1560 PRINT TAB(6);
1570 FOR I=1 TO N
1580 PRINTI;
1590 NEXT I
1600 PRINT
1610 PRINT
1620 FOR I=1 TO N
1630 PRINT I;TAB(6);
1640 FOR J=1 TO N
1650 PRINT E(I,J);
1660 NEXT J
1670 PRINT
1680 NEXT I
1690 PRINT
1700 PRINT"THE COST OF THIS ASSIGNMENT IS"T
1710 PRINT
1720 PRINT
2000 DATA 5
2010 DATA 144,74,46,81,68
2020 DATA 77,27,13,38,28
2030 DATA 107,55,34,60,47
2040 DATA 91,49,31,52,43
2050 DATA 106,38,19,53,44
2060 END