This is an instance of the Carlson and Nemhauser problem of scheduling to minimize interaction cost [1]. The computer program listed below slightly changes the mathematical formulation on page 6 of Heragu and Kusiak [2] and on page 140 of Heragu [3]; its goal is to minimize the total interaction cost of assigning fifteen courses to four time periods, which are period 0, period 1, period 2, and period 3. As the individual interaction costs it uses the interdepartmental flows (of n=20, not n=15) presented in Nugent, Vollmann, and Ruml [4, p. 169]; these flows are used in line 1238 through line 1259 below.
The following computer program benefits from the computer programs of the present blog and the computer program on pages 229-232 of Conley [5].
2 DEFINT I,J,K
5 DIM B(99),N(99),A(99),H(99),L(99),U(99),X(1111),D(111),P(222)
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
21 FOR IOC=1 TO 15
23 B(IOC)=0
24 NEXT IOC
51 FOR IOCTT=1 TO 15
53 N(IOCTT)=3
57 NEXT IOCTT
61 FOR KLQ=1 TO 15
62 A(KLQ)=B(KLQ)+RND*(N(KLQ)-B(KLQ))
63 NEXT KLQ
71 FOR KLR=1 TO 15
72 H(KLR)=3
73 NEXT KLR
88 FOR JJJ=1 TO 1000 STEP 10
90 FOR INEW=1 TO 1
94 FOR J=INEW*2 TO 0 STEP -1
102 FOR JJ=0 TO 15
128 FOR I=1 TO 1
129 FOR KKQQ=1 TO 15
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
132 FOR K=1 TO 15
133 IF RND<=.5 THEN 298 ELSE 230
230 IF A(K)-(N(K)-B(K))/H(K)^J
255 GOTO 265
260 L(K)=A(K)-(N(K)-B(K))/H(K)^J
265 IF A(K)+(N(K)-B(K))/H(K)^J>N(K) THEN 266 ELSE 268
266 U(K)=N(K)-L(K)
267 GOTO 272
268 U(K)=A(K)+(N(K)-B(K))/H(K)^J-L(K)
272 GOTO 300
298 X(K)=A(K)+2*RND*(2*RND-1)*(1/(1+RND*JJJ))*.05*A(K)
299 GOTO 302
300 X(K)=(L(K)+2*RND*RND*U(K))
302 NEXT K
304 X(JJ)=A(JJ)
306 KLPS=FIX(1+RND*45)
307 FOR KLA1=1 TO KLPS
308 KLA2=FIX(1+15*RND)
309 X(KLA2)=A(KLA2)
310 NEXT KLA1
343 IF RND>.1 GOTO 361
352 IF RND<.5 THEN 353 ELSE 355
353 X(JJ)=B(JJ)
354 GOTO 361
355 X(JJ)=N(JJ)
361 FOR I222=1 TO 15
364 X(I222)=FIX(X(I222))
368 NEXT I222
371 FOR I223=1 TO 15
374 IF X(I223)>3 THEN X(I223)=3
378 NEXT I223
381 FOR I224=1 TO 15
384 IF X(I224)<0 THEN X(I224)=0
388 NEXT I224
461 IF RND>.1 GOTO 561
471 IOCT1=1+FIX(RND*15)
474 IOCT2=1+FIX(RND*15)
477 X(IOCT1)=A(IOCT2)
480 X(IOCT2)=A(IOCT1)
561 P(11)=ABS(X(1)-X(2))
562 P(12)=ABS(X(1)-X(3))
563 P(13)=ABS(X(1)-X(4))
564 P(14)=ABS(X(1)-X(5))
565 P(15)=ABS(X(1)-X(6))
566 P(16)=ABS(X(1)-X(7))
567 P(17)=ABS(X(1)-X(8))
568 P(18)=ABS(X(1)-X(9))
569 P(19)=ABS(X(1)-X(10))
570 P(20)=ABS(X(1)-X(11))
571 P(21)=ABS(X(1)-X(12))
572 P(22)=ABS(X(1)-X(13))
573 P(23)=ABS(X(1)-X(14))
574 P(24)=ABS(X(1)-X(15))
580 P(25)=ABS(X(2)-X(3))
581 P(26)=ABS(X(2)-X(4))
582 P(27)=ABS(X(2)-X(5))
583 P(28)=ABS(X(2)-X(6))
584 P(29)=ABS(X(2)-X(7))
585 P(30)=ABS(X(2)-X(8))
586 P(31)=ABS(X(2)-X(9))
587 P(32)=ABS(X(2)-X(10))
588 P(33)=ABS(X(2)-X(11))
589 P(34)=ABS(X(2)-X(12))
590 P(35)=ABS(X(2)-X(13))
591 P(36)=ABS(X(2)-X(14))
592 P(37)=ABS(X(2)-X(15))
598 P(38)=ABS(X(3)-X(4))
599 P(39)=ABS(X(3)-X(5))
600 P(40)=ABS(X(3)-X(6))
601 P(41)=ABS(X(3)-X(7))
602 P(42)=ABS(X(3)-X(8))
603 P(43)=ABS(X(3)-X(9))
604 P(44)=ABS(X(3)-X(10))
605 P(45)=ABS(X(3)-X(11))
606 P(46)=ABS(X(3)-X(12))
607 P(47)=ABS(X(3)-X(13))
608 P(48)=ABS(X(3)-X(14))
609 P(49)=ABS(X(3)-X(15))
615 P(50)=ABS(X(4)-X(5))
616 P(51)=ABS(X(4)-X(6))
617 P(52)=ABS(X(4)-X(7))
618 P(53)=ABS(X(4)-X(8))
619 P(54)=ABS(X(4)-X(9))
620 P(55)=ABS(X(4)-X(10))
621 P(56)=ABS(X(4)-X(11))
622 P(57)=ABS(X(4)-X(12))
623 P(58)=ABS(X(4)-X(13))
624 P(59)=ABS(X(4)-X(14))
625 P(60)=ABS(X(4)-X(15))
631 P(61)=ABS(X(5)-X(6))
632 P(62)=ABS(X(5)-X(7))
633 P(63)=ABS(X(5)-X(8))
634 P(64)=ABS(X(5)-X(9))
635 P(65)=ABS(X(5)-X(10))
636 P(66)=ABS(X(5)-X(11))
637 P(67)=ABS(X(5)-X(12))
638 P(68)=ABS(X(5)-X(13))
639 P(69)=ABS(X(5)-X(14))
640 P(70)=ABS(X(5)-X(15))
646 P(71)=ABS(X(6)-X(7))
647 P(72)=ABS(X(6)-X(8))
648 P(73)=ABS(X(6)-X(9))
649 P(74)=ABS(X(6)-X(10))
650 P(75)=ABS(X(6)-X(11))
651 P(76)=ABS(X(6)-X(12))
652 P(77)=ABS(X(6)-X(13))
653 P(78)=ABS(X(6)-X(14))
654 P(79)=ABS(X(6)-X(15))
660 P(80)=ABS(X(7)-X(8))
661 P(81)=ABS(X(7)-X(9))
662 P(82)=ABS(X(7)-X(10))
663 P(83)=ABS(X(7)-X(11))
664 P(84)=ABS(X(7)-X(12))
665 P(85)=ABS(X(7)-X(13))
666 P(86)=ABS(X(7)-X(14))
667 P(87)=ABS(X(7)-X(15))
673 P(88)=ABS(X(8)-X(9))
674 P(89)=ABS(X(8)-X(10))
675 P(90)=ABS(X(8)-X(11))
676 P(91)=ABS(X(8)-X(12))
677 P(92)=ABS(X(8)-X(13))
678 P(93)=ABS(X(8)-X(14))
679 P(94)=ABS(X(8)-X(15))
685 P(95)=ABS(X(9)-X(10))
686 P(96)=ABS(X(9)-X(11))
687 P(97)=ABS(X(9)-X(12))
688 P(98)=ABS(X(9)-X(13))
689 P(99)=ABS(X(9)-X(14))
690 P(100)=ABS(X(9)-X(15))
696 P(101)=ABS(X(10)-X(11))
697 P(102)=ABS(X(10)-X(12))
698 P(103)=ABS(X(10)-X(13))
699 P(104)=ABS(X(10)-X(14))
700 P(105)=ABS(X(10)-X(15))
706 P(106)=ABS(X(11)-X(12))
707 P(107)=ABS(X(11)-X(13))
708 P(108)=ABS(X(11)-X(14))
709 P(109)=ABS(X(11)-X(15))
715 P(110)=ABS(X(12)-X(13))
716 P(111)=ABS(X(12)-X(14))
717 P(112)=ABS(X(12)-X(15))
723 P(113)=ABS(X(13)-X(14))
724 P(114)=ABS(X(13)-X(15))
730 P(115)=ABS(X(14)-X(15))
788 FOR INSI=11 TO 115
791 IF P(INSI)<.5 THEN P(INSI)=1 ELSE P(INSI)=0
795 NEXT INSI
1238 P11B=0*P(11)+5*P(12)+0*P(13)+5*P(14)+2*P(15)+10*P(16)+3*P(17)+1*P(18)+5*P(19)+5*P(20)
1239 P12B=5*P(21)+0*P(22)+0*P(23)+5*P(24)
1240 P13B=3*P(25)+10*P(26)+5*P(27)+1*P(28)+5*P(29)+1*P(30)+2*P(31)+4*P(32)+2*P(33)
1241 P14B=5*P(34)+0*P(35)+10*P(36)+10*P(37)
1243 P15B=2*P(38)+0*P(39)+5*P(40)+2*P(41)+4*P(42)+4*P(43)+5*P(44)+0*P(45)
1244 P16B=0*P(46)+0*P(47)+5*P(48)+1*P(49)
1245 P17B=1*P(50)+0*P(51)+5*P(52)+2*P(53)+1*P(54)+0*P(55)+10*P(56)
1246 P18B=2*P(57)+2*P(58)+0*P(59)+2*P(60)
1248 P19B=5*P(61)+6*P(62)+5*P(63)+2*P(64)+5*P(65)+2*P(66)+0*P(67)+5*P(68)+1*P(69)+1*P(70)
1249 P20B=5*P(71)+2*P(72)+1*P(73)+6*P(74)+0*P(75)+0*P(76)+10*P(77)+0*P(78)+2*P(79)
1250 P21B=0*P(80)+0*P(81)+0*P(82)+5*P(83)+10*P(84)+2*P(85)+2*P(86)+5*P(87)
1251 P22B=1*P(88)+1*P(89)+10*P(90)+10*P(91)+2*P(92)+0*P(93)+10*P(94)
1255 P23B=2*P(95)+0*P(96)+3*P(97)+5*P(98)+5*P(99)+0*P(100)
1257 P24B=5*P(101)+5*P(102)+0*P(103)+5*P(104)+1*P(105)
1258 P25B=5*P(106)+2*P(107)+5*P(108)+1*P(109)
1259 P26B=2*P(110)+10*P(111)+5*P(112)+2*P(113)+2*P(114)+5*P(115)
1445 P1=P11B+P12B+P13B+P14B+P15B+P16B+P17B+P18B+P19B+P20B+P21B+P22B+P23B+P24B+P25B+P26B
1446 P2=0
1448 P3=P1+P2
1450 P=-P3+PS1
1451 IF P<=M THEN 1670
1452 M=P
1453 PP1=P3
1454 FOR KLX=1 TO 15
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1457 GOTO 128
1670 NEXT I
1702 NEXT JJ
1706 NEXT J
1777 NEXT INEW
1888 NEXT JJJ
1890 IF M>-9999 THEN 1916 ELSE 1999
1916 PRINT JJJJ,M,PP1
1917 PRINT A(1),A(2),A(3),A(4),A(5)
1918 PRINT A(6),A(7),A(8),A(9),A(10)
1920 PRINT A(11),A(12),A(13),A(14),A(15)
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the candidate solutions produced from JJJJ=-32000 through JJJJ=-31995 (in compressed form and to be interpreted in accordance with line 1916 through line 1920; copied manually from the computer monitor) are presented below.
-32000 -20 20
0 0 2 3 2
3 1 1 3 1
2 3 0 1 2
-31999 -21 21
0 2 1 0 1
0 2 2 2 3
1 1 3 0 3
-31998 -17 17
2 0 1 2 1
2 3 3 3 3
0 1 0 2 1
-31997 -17 17
0 3 2 0 2
0 1 1 1 1
3 2 3 0 2
-31996 -17 17
1 0 2 1 2
1 3 3 3 3
0 2 0 1 2
-31995 -18 18
1 0 3 1 3
1 0 0 2 0
2 3 0 1 2
Among the candidate solutions presented above, the best are at JJJJ=-31998, JJJJ=-31997, and JJJJ=-31996 with an objective function value of 17.
The output above was produced in one minute on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter, which is slower than the corresponding compiler.
References
[1] R.C. Carlson, G.L. Nemhauser, Scheduling to minimize interaction cost, Operations Research 14 (1966) 52-58.
[2] S.S. Heragu, A. Kusiak, Efficient models for the facility layout problem, European Journal of Operational Research 53 (1991) 1-13.
[3] S.S. Heragu, Recent models and techniques for solving the layout problem, European Journal of Operational Research 57 (1992) 136-144.
[4] C.E. Nugent, T.E. Vollmann, J. Ruml, An experimental comparison of techniques for the assignment of facilities to locations, Operations Research 16 (1968) 150-173.
[5] W.C. Conley, Optimization: A Simplified Approach, Petrocelli, Princeton, New Jersey, 1981.
