Jsun Yui Wong
The difference between the original Carlson and Nemhauser problem [1] and the problem of Davis,
Devine, and Lutz [2] is "that their problem did not consider conflicting facilities," Davis, Devine, and Lutz [2, p. 225]. For the newer problem, "a cost is incurred if two activities are assigned to the same facility, or to two facilities whose operation is in conflict," Davis et al. [2, p. 224]. Dealing with an instance of the newer problem, the computer program below attempts to find the lowest cost of scheduling twelve courses in four time periods with the following condition: the operation of period 1 and period 2 is in conflict, and the operation of period 2 and period 3 is in conflict. These two conflicts are specified in line 6, line 7, and line 8 below.
The costs used in line 1001 through line 1066 of the computer program below come from Hillier [3] and Nugent, Vollmann, and Ruml [4].
In this paper, A(1)=1, A(2)=1, A(3)=1,..., and A(12)=1 stand for course 1 in period 1, course 2 in period 1, course 3 in period 1,..., and course 12 in period 1, respectively.
The computer program below is modelled after the computer program of the post "Assigning Activities to Conflicting Facilities To Minimize Conflict Cost" of the present blog.
2 DEFINT A-Z
3 DEFDBL M,T,P
4 DIM TBM(6,6)
5 DIM N(9),B(9),A(199),H(99),X(199),P(450),L(99),U(99),Q(977),R(444),T(137),Q1(222)
6 TBM(1,1)=1:TBM(1,2)=1:TBM(1,3)=0
7 TBM(2,1)=1:TBM(2,2)=1:TBM(2,3)=1
8 TBM(3,1)=0:TBM(3,2)=1:TBM(3,3)=1
9 TBM(4,4)=1
12 FOR JJJJ=-32000 TO 32000
14 RANDOMIZE JJJJ
16 M=-1D+17
83 A(1)=1:A(2)=1:A(3)=1:A(4)=1:A(5)=2:A(6)=2:A(7)=2
84 A(8)=2:A(9)=3:A(10)=3:A(11)=3:A(12)=3
126 IMAR=10+FIX(RND*1000)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 12
131 X(K)=A(K)
132 NEXT K
241 IAP1=1+FIX(RND*12)
243 X(IAP1)=1+FIX(RND*4)
1001 T(1)=5*10000*(1/(10000*(1-TBM(X(1),X(2)))+1))
1002 T(2)=2*10000*(1/(10000*(1-TBM(X(1),X(3)))+1))
1003 T(3)=4*10000*(1/(10000*(1-TBM(X(1),X(4)))+1))
1004 T(4)=1*10000*(1/(10000*(1-TBM(X(1),X(5)))+1))
1005 T(5)=0*10000*(1/(10000*(1-TBM(X(1),X(6)))+1))
1006 T(6)=0*10000*(1/(10000*(1-TBM(X(1),X(7)))+1))
1007 T(7)=6*10000*(1/(10000*(1-TBM(X(1),X(8)))+1))
1008 T(8)=2*10000*(1/(10000*(1-TBM(X(1),X(9)))+1))
1009 T(9)=1*10000*(1/(10000*(1-TBM(X(1),X(10)))+1))
1010 T(10)=1*10000*(1/(10000*(1-TBM(X(1),X(11)))+1))
1011 T(11)=1*10000*(1/(10000*(1-TBM(X(1),X(12)))+1))
1012 T(12)=3*10000*(1/(10000*(1-TBM(X(2),X(3)))+1))
1013 T(13)=0*10000*(1/(10000*(1-TBM(X(2),X(4)))+1))
1014 T(14)=2*10000*(1/(10000*(1-TBM(X(2),X(5)))+1))
1015 T(15)=2*10000*(1/(10000*(1-TBM(X(2),X(6)))+1))
1016 T(16)=2*10000*(1/(10000*(1-TBM(X(2),X(7)))+1))
1017 T(17)=0*10000*(1/(10000*(1-TBM(X(2),X(8)))+1))
1018 T(18)=4*10000*(1/(10000*(1-TBM(X(2),X(9)))+1))
1019 T(19)=5*10000*(1/(10000*(1-TBM(X(2),X(10)))+1))
1020 T(20)=0*10000*(1/(10000*(1-TBM(X(2),X(11)))+1))
1021 T(21)=0*10000*(1/(10000*(1-TBM(X(2),X(12)))+1))
1022 T(22)=0*10000*(1/(10000*(1-TBM(X(3),X(4)))+1))
1023 T(23)=0*10000*(1/(10000*(1-TBM(X(3),X(5)))+1))
1024 T(24)=0*10000*(1/(10000*(1-TBM(X(3),X(6)))+1))
1025 T(25)=0*10000*(1/(10000*(1-TBM(X(3),X(7)))+1))
1026 T(26)=5*10000*(1/(10000*(1-TBM(X(3),X(8)))+1))
1027 T(27)=5*10000*(1/(10000*(1-TBM(X(3),X(9)))+1))
1028 T(28)=2*10000*(1/(10000*(1-TBM(X(3),X(10)))+1))
1029 T(29)=2*10000*(1/(10000*(1-TBM(X(3),X(11)))+1))
1030 T(30)=2*10000*(1/(10000*(1-TBM(X(3),X(12)))+1))
1031 T(31)=5*10000*(1/(10000*(1-TBM(X(4),X(5)))+1))
1032 T(32)=2*10000*(1/(10000*(1-TBM(X(4),X(6)))+1))
1033 T(33)=2*10000*(1/(10000*(1-TBM(X(4),X(7)))+1))
1034 T(34)=10*10000*(1/(10000*(1-TBM(X(4),X(8)))+1))
1035 T(35)=0*10000*(1/(10000*(1-TBM(X(4),X(9)))+1))
1036 T(36)=0*10000*(1/(10000*(1-TBM(X(4),X(10)))+1))
1037 T(37)=5*10000*(1/(10000*(1-TBM(X(4),X(11)))+1))
1038 T(38)=5*10000*(1/(10000*(1-TBM(X(4),X(12)))+1))
1039 T(39)=10*10000*(1/(10000*(1-TBM(X(5),X(6)))+1))
1040 T(40)=0*10000*(1/(10000*(1-TBM(X(5),X(7)))+1))
1041 T(41)=0*10000*(1/(10000*(1-TBM(X(5),X(8)))+1))
1042 T(42)=0*10000*(1/(10000*(1-TBM(X(5),X(9)))+1))
1043 T(43)=5*10000*(1/(10000*(1-TBM(X(5),X(10)))+1))
1044 T(44)=1*10000*(1/(10000*(1-TBM(X(5),X(11)))+1))
1045 T(45)=1*10000*(1/(10000*(1-TBM(X(5),X(12)))+1))
1046 T(46)=5*10000*(1/(10000*(1-TBM(X(6),X(7)))+1))
1047 T(47)=1*10000*(1/(10000*(1-TBM(X(6),X(8)))+1))
1048 T(48)=1*10000*(1/(10000*(1-TBM(X(6),X(9)))+1))
1049 T(49)=5*10000*(1/(10000*(1-TBM(X(6),X(10)))+1))
1050 T(50)=4*10000*(1/(10000*(1-TBM(X(6),X(11)))+1))
1051 T(51)=0*10000*(1/(10000*(1-TBM(X(6),X(12)))+1))
1052 T(52)=10*10000*(1/(10000*(1-TBM(X(7),X(8)))+1))
1053 T(53)=5*10000*(1/(10000*(1-TBM(X(7),X(9)))+1))
1054 T(54)=2*10000*(1/(10000*(1-TBM(X(7),X(10)))+1))
1055 T(55)=3*10000*(1/(10000*(1-TBM(X(7),X(11)))+1))
1056 T(56)=3*10000*(1/(10000*(1-TBM(X(7),X(12)))+1))
1057 T(57)=0*10000*(1/(10000*(1-TBM(X(8),X(9)))+1))
1058 T(58)=0*10000*(1/(10000*(1-TBM(X(8),X(10)))+1))
1059 T(59)=5*10000*(1/(10000*(1-TBM(X(8),X(11)))+1))
1060 T(60)=0*10000*(1/(10000*(1-TBM(X(8),X(12)))+1))
1061 T(61)=0*10000*(1/(10000*(1-TBM(X(9),X(10)))+1))
1062 T(62)=10*10000*(1/(10000*(1-TBM(X(9),X(11)))+1))
1063 T(63)=10*10000*(1/(10000*(1-TBM(X(9),X(12)))+1))
1064 T(64)=5*10000*(1/(10000*(1-TBM(X(10),X(11)))+1))
1065 T(65)=0*10000*(1/(10000*(1-TBM(X(10),X(12)))+1))
1066 T(66)=2*10000*(1/(10000*(1-TBM(X(11),X(12)))+1))
1151 P1NEW=0
1152 FOR KAU7=1 TO 66
1153 P1NEW=P1NEW+T(KAU7)
1154 NEXT KAU7
1450 P=-P1NEW
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 12
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1666 GOTO 128
1670 NEXT I
1890 IF M>-160000! THEN 1911 ELSE 1999
1911 PRINT A(1),A(2),A(3)
1912 PRINT A(4),A(5),A(6)
1913 PRINT A(7),A(8),A(9)
1914 PRINT A(10),A(11),A(12),JJJJ,M
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its output through JJJJ=-31990 is presented below.
1 4 1
3 1 4
1 4 3
3 1 4 -31996 -130160.9839016098
3 4 3
1 3 4
3 4 1
1 3 4 -31993 -130160.9839016098
3 1 3
4 3 1
3 1 4
4 3 1 -31992 -130160.9839016098
3 1 3
4 3 1
3 1 4
4 3 1 -31991 -130160.9839016098
1 3 1
4 1 3
1 3 4
4 1 3 -31990 -130160.9839016098
The output above was produced in 5 seconds 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] F. E. Davis, M. D. Devine, R. P. Lutz, Scheduling activities among conflicting facilities to minimize conflict, Mathematical Programming 6 (1974) 224-228.
[3] F. S. Hillier, Quantitative tools for plant layout analysis, J. Indust. Eng. 14 (1963) 33-40.
[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.
Wednesday, January 28, 2009
Subscribe to:
Posts (Atom)