Jsun Yui Wong
The example used in this paper to illustrate the computer program listed here is based on Carlson and Nemhauser [1],
Davis et al. [2], and Lutz et al. [3]. This computer program is concerned with a problem of scheduling activities among conflicting facilities to minimize conflict cost; a conflict cost arises when two activities are assigned to the same facility or to two facilities operating in conflict. This problem is a generalization of the original Carlson and Nemhauser problem to minimize interaction cost [1]; an intervention cost arises when, for example, two courses are scheduled during the same time period. The difference between the original Carlson and Nemhauser problem and the problem of Davis et al. is "that their problem did not consider conflicting facilities," [2, Davis et al.].
Specifically this computer program in BASIC deals with a case of assigning thirty courses (activities) to six time blocks (facilities) to minimize conflict cost, given the interdepartmental flows of the Nug30 problem as the conflict costs of all pairs of courses [4, Nugent et al., p. 170]. Time block 1 and time block 2 operate in conflict; time block 2 and time block 3 also operate in conflict. Courses 1 through 14 may be assigned to time blocks 1, 2, and 3, courses 15 through 23 may be assigned in time blocks 2, 3, and 4, and courses 24 through 30 may be assigned to time blocks 4, 5, and 6.
Lines 71 through 95 of the following computer program are a precautionary measure againt having a very bad inputted initial feasible solution. (An examlpe of an inputted initial feasible solution is shown in line 51 through line 55.) This precautionary measure may or may not be helpful for this problem, but it may be helpful for other problems. Lines 71 through 95 are just an example; these can be properly replaced by other lines.
2 DEFINT I,J,K
3 DIM TBM(7,7)
7 DIM AZ(50),A(99),X(99),P(450),T(500)
32 TBM(1,1)=1:TBM(1,2)=1
33 TBM(2,1)=1:TBM(2,2)=1:TBM(2,3)=1
34 TBM(3,2)=1:TBM(3,3)=1
35 TBM(4,4)=1
36 TBM(5,5)=1
37 TBM(6,6)=1
51 A(1)=1:A(2)=1:A(3)=1:A(4)=1:A(5)=1:A(6)=1
52 A(7)=1:A(8)=1:A(9)=1:A(10)=1:A(11)=1:A(12)=1
53 A(13)=1:A(14)=1:A(15)=2:A(16)=2:A(17)=2:A(18)=2
54 A(19)=2:A(20)=2:A(21)=2:A(22)=2:A(23)=2:A(24)=4
55 A(25)=4:A(26)=4:A(27)=4:A(28)=4:A(29)=4:A(30)=4
62 FOR JJJJ=-32000 TO 32000
64 RANDOMIZE JJJJ
66 M=-1D+17
71 FOR IALT=1 TO 28
78 AHOS=1+FIX(RND*14):BHOS=1+FIX(RND*14)
80 AZ(AHOS)=A(AHOS)
83 A(AHOS)=A(BHOS)
86 A(BHOS)=AZ(AHOS)
89 NEXT IALT
93 A(15)=2:A(16)=2:A(17)=2:A(18)=2
94 A(19)=2:A(20)=2:A(21)=2:A(22)=2:A(23)=2:A(24)=4
95 A(25)=4:A(26)=4:A(27)=4:A(28)=4:A(29)=4:A(30)=4
111 IMAR=50+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR K=1 TO 30
301 X(K)=A(K)
302 NEXT K
311 IF RND<.3333 THEN 341 ELSE IF RND<.5 THEN 351 ELSE 361
341 IAP1=1+FIX(RND*14)
343 X(IAP1)=1+FIX(RND*3)
346 GOTO 401
351 IAP2=15+FIX(RND*9)
353 X(IAP2)=2+FIX(RND*3)
356 GOTO 401
361 IAP3=24+FIX(RND*7)
363 X(IAP3)=4+FIX(RND*3)
401 T(1)=3*10000*(1/(10000*(1-TBM(X(1),X(2)))+1))
402 T(2)=2*10000*(1/(10000*(1-TBM(X(1),X(3)))+1))
403 T(3)=0*10000*(1/(10000*(1-TBM(X(1),X(4)))+1))
404 T(4)=0*10000*(1/(10000*(1-TBM(X(1),X(5)))+1))
405 T(5)=2*10000*(1/(10000*(1-TBM(X(1),X(6)))+1))
406 T(6)=10*10000*(1/(10000*(1-TBM(X(1),X(7)))+1))
407 T(7)=5*10000*(1/(10000*(1-TBM(X(1),X(8)))+1))
408 T(8)=0*10000*(1/(10000*(1-TBM(X(1),X(9)))+1))
409 T(9)=5*10000*(1/(10000*(1-TBM(X(1),X(10)))+1))
410 T(10)=2*10000*(1/(10000*(1-TBM(X(1),X(11)))+1))
411 T(11)=5*10000*(1/(10000*(1-TBM(X(1),X(12)))+1))
412 T(12)=0*10000*(1/(10000*(1-TBM(X(1),X(13)))+1))
413 T(13)=0*10000*(1/(10000*(1-TBM(X(1),X(14)))+1))
414 T(14)=2*10000*(1/(10000*(1-TBM(X(1),X(15)))+1))
415 T(15)=0*10000*(1/(10000*(1-TBM(X(1),X(16)))+1))
416 T(16)=5*10000*(1/(10000*(1-TBM(X(1),X(17)))+1))
417 T(17)=6*10000*(1/(10000*(1-TBM(X(1),X(18)))+1))
418 T(18)=3*10000*(1/(10000*(1-TBM(X(1),X(19)))+1))
419 T(19)=0*10000*(1/(10000*(1-TBM(X(1),X(20)))+1))
420 T(20)=1*10000*(1/(10000*(1-TBM(X(1),X(21)))+1))
421 T(21)=10*10000*(1/(10000*(1-TBM(X(1),X(22)))+1))
422 T(22)=0*10000*(1/(10000*(1-TBM(X(1),X(23)))+1))
423 T(23)=10*10000*(1/(10000*(1-TBM(X(1),X(24)))+1))
424 T(24)=2*10000*(1/(10000*(1-TBM(X(1),X(25)))+1))
425 T(25)=1*10000*(1/(10000*(1-TBM(X(1),X(26)))+1))
426 T(26)=1*10000*(1/(10000*(1-TBM(X(1),X(27)))+1))
427 T(27)=1*10000*(1/(10000*(1-TBM(X(1),X(28)))+1))
428 T(28)=0*10000*(1/(10000*(1-TBM(X(1),X(29)))+1))
429 T(29)=1*10000*(1/(10000*(1-TBM(X(1),X(30)))+1))
430 T(30)=4*10000*(1/(10000*(1-TBM(X(2),X(3)))+1))
431 T(31)=0*10000*(1/(10000*(1-TBM(X(2),X(4)))+1))
432 T(32)=10*10000*(1/(10000*(1-TBM(X(2),X(5)))+1))
433 T(33)=4*10000*(1/(10000*(1-TBM(X(2),X(6)))+1))
434 T(34)=0*10000*(1/(10000*(1-TBM(X(2),X(7)))+1))
435 T(35)=0*10000*(1/(10000*(1-TBM(X(2),X(8)))+1))
436 T(36)=2*10000*(1/(10000*(1-TBM(X(2),X(9)))+1))
437 T(37)=2*10000*(1/(10000*(1-TBM(X(2),X(10)))+1))
438 T(38)=1*10000*(1/(10000*(1-TBM(X(2),X(11)))+1))
439 T(39)=0*10000*(1/(10000*(1-TBM(X(2),X(12)))+1))
440 T(40)=5*10000*(1/(10000*(1-TBM(X(2),X(13)))+1))
441 T(41)=0*10000*(1/(10000*(1-TBM(X(2),X(14)))+1))
442 T(42)=0*10000*(1/(10000*(1-TBM(X(2),X(15)))+1))
443 T(43)=0*10000*(1/(10000*(1-TBM(X(2),X(16)))+1))
444 T(44)=0*10000*(1/(10000*(1-TBM(X(2),X(17)))+1))
445 T(45)=2*10000*(1/(10000*(1-TBM(X(2),X(18)))+1))
446 T(46)=0*10000*(1/(10000*(1-TBM(X(2),X(19)))+1))
447 T(47)=1*10000*(1/(10000*(1-TBM(X(2),X(20)))+1))
448 T(48)=6*10000*(1/(10000*(1-TBM(X(2),X(21)))+1))
449 T(49)=1*10000*(1/(10000*(1-TBM(X(2),X(22)))+1))
450 T(50)=0*10000*(1/(10000*(1-TBM(X(2),X(23)))+1))
451 T(51)=1*10000*(1/(10000*(1-TBM(X(2),X(24)))+1))
452 T(52)=2*10000*(1/(10000*(1-TBM(X(2),X(25)))+1))
453 T(53)=2*10000*(1/(10000*(1-TBM(X(2),X(26)))+1))
454 T(54)=5*10000*(1/(10000*(1-TBM(X(2),X(27)))+1))
455 T(55)=1*10000*(1/(10000*(1-TBM(X(2),X(28)))+1))
456 T(56)=10*10000*(1/(10000*(1-TBM(X(2),X(29)))+1))
457 T(57)=5*10000*(1/(10000*(1-TBM(X(2),X(30)))+1))
458 T(58)=3*10000*(1/(10000*(1-TBM(X(3),X(4)))+1))
459 T(59)=4*10000*(1/(10000*(1-TBM(X(3),X(5)))+1))
460 T(60)=0*10000*(1/(10000*(1-TBM(X(3),X(6)))+1))
461 T(61)=5*10000*(1/(10000*(1-TBM(X(3),X(7)))+1))
462 T(62)=5*10000*(1/(10000*(1-TBM(X(3),X(8)))+1))
463 T(63)=5*10000*(1/(10000*(1-TBM(X(3),X(9)))+1))
464 T(64)=1*10000*(1/(10000*(1-TBM(X(3),X(10)))+1))
465 T(65)=4*10000*(1/(10000*(1-TBM(X(3),X(11)))+1))
466 T(66)=1*10000*(1/(10000*(1-TBM(X(3),X(12)))+1))
467 T(67)=0*10000*(1/(10000*(1-TBM(X(3),X(13)))+1))
468 T(68)=4*10000*(1/(10000*(1-TBM(X(3),X(14)))+1))
469 T(69)=0*10000*(1/(10000*(1-TBM(X(3),X(15)))+1))
470 T(70)=4*10000*(1/(10000*(1-TBM(X(3),X(16)))+1))
471 T(71)=0*10000*(1/(10000*(1-TBM(X(3),X(17)))+1))
472 T(72)=6*10000*(1/(10000*(1-TBM(X(3),X(18)))+1))
473 T(73)=3*10000*(1/(10000*(1-TBM(X(3),X(19)))+1))
474 T(74)=2*10000*(1/(10000*(1-TBM(X(3),X(20)))+1))
475 T(75)=5*10000*(1/(10000*(1-TBM(X(3),X(21)))+1))
476 T(76)=5*10000*(1/(10000*(1-TBM(X(3),X(22)))+1))
477 T(77)=2*10000*(1/(10000*(1-TBM(X(3),X(23)))+1))
478 T(78)=1*10000*(1/(10000*(1-TBM(X(3),X(24)))+1))
479 T(79)=0*10000*(1/(10000*(1-TBM(X(3),X(25)))+1))
480 T(80)=0*10000*(1/(10000*(1-TBM(X(3),X(26)))+1))
481 T(81)=3*10000*(1/(10000*(1-TBM(X(3),X(27)))+1))
482 T(82)=1*10000*(1/(10000*(1-TBM(X(3),X(28)))+1))
483 T(83)=0*10000*(1/(10000*(1-TBM(X(3),X(29)))+1))
484 T(84)=2*10000*(1/(10000*(1-TBM(X(3),X(30)))+1))
485 T(85)=0*10000*(1/(10000*(1-TBM(X(4),X(5)))+1))
486 T(86)=0*10000*(1/(10000*(1-TBM(X(4),X(6)))+1))
487 T(87)=0*10000*(1/(10000*(1-TBM(X(4),X(7)))+1))
488 T(88)=2*10000*(1/(10000*(1-TBM(X(4),X(8)))+1))
489 T(89)=2*10000*(1/(10000*(1-TBM(X(4),X(9)))+1))
490 T(90)=0*10000*(1/(10000*(1-TBM(X(4),X(10)))+1))
491 T(91)=6*10000*(1/(10000*(1-TBM(X(4),X(11)))+1))
492 T(92)=0*10000*(1/(10000*(1-TBM(X(4),X(12)))+1))
493 T(93)=2*10000*(1/(10000*(1-TBM(X(4),X(13)))+1))
494 T(94)=5*10000*(1/(10000*(1-TBM(X(4),X(14)))+1))
495 T(95)=2*10000*(1/(10000*(1-TBM(X(4),X(15)))+1))
496 T(96)=5*10000*(1/(10000*(1-TBM(X(4),X(16)))+1))
497 T(97)=1*10000*(1/(10000*(1-TBM(X(4),X(17)))+1))
498 T(98)=1*10000*(1/(10000*(1-TBM(X(4),X(18)))+1))
499 T(99)=1*10000*(1/(10000*(1-TBM(X(4),X(19)))+1))
500 T(100)=1*10000*(1/(10000*(1-TBM(X(4),X(20)))+1))
501 T(101)=2*10000*(1/(10000*(1-TBM(X(4),X(21)))+1))
502 T(102)=2*10000*(1/(10000*(1-TBM(X(4),X(22)))+1))
503 T(103)=4*10000*(1/(10000*(1-TBM(X(4),X(23)))+1))
504 T(104)=0*10000*(1/(10000*(1-TBM(X(4),X(24)))+1))
505 T(105)=2*10000*(1/(10000*(1-TBM(X(4),X(25)))+1))
506 T(106)=0*10000*(1/(10000*(1-TBM(X(4),X(26)))+1))
507 T(107)=2*10000*(1/(10000*(1-TBM(X(4),X(27)))+1))
508 T(108)=2*10000*(1/(10000*(1-TBM(X(4),X(28)))+1))
509 T(109)=5*10000*(1/(10000*(1-TBM(X(4),X(29)))+1))
510 T(110)=5*10000*(1/(10000*(1-TBM(X(4),X(30)))+1))
511 T(111)=5*10000*(1/(10000*(1-TBM(X(5),X(6)))+1))
512 T(112)=2*10000*(1/(10000*(1-TBM(X(5),X(7)))+1))
513 T(113)=0*10000*(1/(10000*(1-TBM(X(5),X(8)))+1))
514 T(114)=0*10000*(1/(10000*(1-TBM(X(5),X(9)))+1))
515 T(115)=0*10000*(1/(10000*(1-TBM(X(5),X(10)))+1))
516 T(116)=0*10000*(1/(10000*(1-TBM(X(5),X(11)))+1))
517 T(117)=2*10000*(1/(10000*(1-TBM(X(5),X(12)))+1))
518 T(118)=0*10000*(1/(10000*(1-TBM(X(5),X(13)))+1))
519 T(119)=0*10000*(1/(10000*(1-TBM(X(5),X(14)))+1))
520 T(120)=0*10000*(1/(10000*(1-TBM(X(5),X(15)))+1))
521 T(121)=0*10000*(1/(10000*(1-TBM(X(5),X(16)))+1))
522 T(122)=2*10000*(1/(10000*(1-TBM(X(5),X(17)))+1))
523 T(123)=1*10000*(1/(10000*(1-TBM(X(5),X(18)))+1))
524 T(124)=0*10000*(1/(10000*(1-TBM(X(5),X(19)))+1))
525 T(125)=0*10000*(1/(10000*(1-TBM(X(5),X(20)))+1))
526 T(126)=2*10000*(1/(10000*(1-TBM(X(5),X(21)))+1))
527 T(127)=0*10000*(1/(10000*(1-TBM(X(5),X(22)))+1))
528 T(128)=5*10000*(1/(10000*(1-TBM(X(5),X(23)))+1))
529 T(129)=1*10000*(1/(10000*(1-TBM(X(5),X(24)))+1))
530 T(130)=0*10000*(1/(10000*(1-TBM(X(5),X(25)))+1))
531 T(131)=2*10000*(1/(10000*(1-TBM(X(5),X(26)))+1))
532 T(132)=1*10000*(1/(10000*(1-TBM(X(5),X(27)))+1))
533 T(133)=0*10000*(1/(10000*(1-TBM(X(5),X(28)))+1))
534 T(134)=2*10000*(1/(10000*(1-TBM(X(5),X(29)))+1))
535 T(135)=1*10000*(1/(10000*(1-TBM(X(5),X(30)))+1))
536 T(136)=1*10000*(1/(10000*(1-TBM(X(6),X(7)))+1))
537 T(137)=2*10000*(1/(10000*(1-TBM(X(6),X(8)))+1))
538 T(138)=2*10000*(1/(10000*(1-TBM(X(6),X(9)))+1))
539 T(139)=1*10000*(1/(10000*(1-TBM(X(6),X(10)))+1))
540 T(140)=4*10000*(1/(10000*(1-TBM(X(6),X(11)))+1))
541 T(141)=10*10000*(1/(10000*(1-TBM(X(6),X(12)))+1))
542 T(142)=10*10000*(1/(10000*(1-TBM(X(6),X(13)))+1))
543 T(143)=2*10000*(1/(10000*(1-TBM(X(6),X(14)))+1))
544 T(144)=5*10000*(1/(10000*(1-TBM(X(6),X(15)))+1))
545 T(145)=5*10000*(1/(10000*(1-TBM(X(6),X(16)))+1))
546 T(146)=0*10000*(1/(10000*(1-TBM(X(6),X(17)))+1))
547 T(147)=5*10000*(1/(10000*(1-TBM(X(6),X(18)))+1))
548 T(148)=0*10000*(1/(10000*(1-TBM(X(6),X(19)))+1))
549 T(149)=0*10000*(1/(10000*(1-TBM(X(6),X(20)))+1))
550 T(150)=0*10000*(1/(10000*(1-TBM(X(6),X(21)))+1))
551 T(151)=10*10000*(1/(10000*(1-TBM(X(6),X(22)))+1))
552 T(152)=0*10000*(1/(10000*(1-TBM(X(6),X(23)))+1))
553 T(153)=0*10000*(1/(10000*(1-TBM(X(6),X(24)))+1))
554 T(154)=0*10000*(1/(10000*(1-TBM(X(6),X(25)))+1))
555 T(155)=4*10000*(1/(10000*(1-TBM(X(6),X(26)))+1))
556 T(156)=0*10000*(1/(10000*(1-TBM(X(6),X(27)))+1))
557 T(157)=10*10000*(1/(10000*(1-TBM(X(6),X(28)))+1))
558 T(158)=1*10000*(1/(10000*(1-TBM(X(6),X(29)))+1))
559 T(159)=1*10000*(1/(10000*(1-TBM(X(6),X(30)))+1))
560 T(160)=10*10000*(1/(10000*(1-TBM(X(7),X(8)))+1))
561 T(161)=10*10000*(1/(10000*(1-TBM(X(7),X(9)))+1))
562 T(162)=5*10000*(1/(10000*(1-TBM(X(7),X(10)))+1))
563 T(163)=10*10000*(1/(10000*(1-TBM(X(7),X(11)))+1))
564 T(164)=10*10000*(1/(10000*(1-TBM(X(7),X(12)))+1))
565 T(165)=6*10000*(1/(10000*(1-TBM(X(7),X(13)))+1))
566 T(166)=0*10000*(1/(10000*(1-TBM(X(7),X(14)))+1))
567 T(167)=0*10000*(1/(10000*(1-TBM(X(7),X(15)))+1))
568 T(168)=10*10000*(1/(10000*(1-TBM(X(7),X(16)))+1))
569 T(169)=2*10000*(1/(10000*(1-TBM(X(7),X(17)))+1))
570 T(170)=1*10000*(1/(10000*(1-TBM(X(7),X(18)))+1))
571 T(171)=10*10000*(1/(10000*(1-TBM(X(7),X(19)))+1))
572 T(172)=1*10000*(1/(10000*(1-TBM(X(7),X(20)))+1))
573 T(173)=5*10000*(1/(10000*(1-TBM(X(7),X(21)))+1))
574 T(174)=5*10000*(1/(10000*(1-TBM(X(7),X(22)))+1))
575 T(175)=2*10000*(1/(10000*(1-TBM(X(7),X(23)))+1))
576 T(176)=3*10000*(1/(10000*(1-TBM(X(7),X(24)))+1))
577 T(177)=5*10000*(1/(10000*(1-TBM(X(7),X(25)))+1))
578 T(178)=0*10000*(1/(10000*(1-TBM(X(7),X(26)))+1))
579 T(179)=2*10000*(1/(10000*(1-TBM(X(7),X(27)))+1))
580 T(180)=0*10000*(1/(10000*(1-TBM(X(7),X(28)))+1))
581 T(181)=1*10000*(1/(10000*(1-TBM(X(7),X(29)))+1))
582 T(182)=3*10000*(1/(10000*(1-TBM(X(7),X(30)))+1))
583 T(183)=1*10000*(1/(10000*(1-TBM(X(8),X(9)))+1))
584 T(184)=3*10000*(1/(10000*(1-TBM(X(8),X(10)))+1))
585 T(185)=5*10000*(1/(10000*(1-TBM(X(8),X(11)))+1))
586 T(186)=0*10000*(1/(10000*(1-TBM(X(8),X(12)))+1))
587 T(187)=0*10000*(1/(10000*(1-TBM(X(8),X(13)))+1))
588 T(188)=0*10000*(1/(10000*(1-TBM(X(8),X(14)))+1))
589 T(189)=2*10000*(1/(10000*(1-TBM(X(8),X(15)))+1))
590 T(190)=4*10000*(1/(10000*(1-TBM(X(8),X(16)))+1))
591 T(191)=5*10000*(1/(10000*(1-TBM(X(8),X(17)))+1))
592 T(192)=2*10000*(1/(10000*(1-TBM(X(8),X(18)))+1))
593 T(193)=10*10000*(1/(10000*(1-TBM(X(8),X(19)))+1))
594 T(194)=6*10000*(1/(10000*(1-TBM(X(8),X(20)))+1))
595 T(195)=0*10000*(1/(10000*(1-TBM(X(8),X(21)))+1))
596 T(196)=5*10000*(1/(10000*(1-TBM(X(8),X(22)))+1))
597 T(197)=5*10000*(1/(10000*(1-TBM(X(8),X(23)))+1))
598 T(198)=2*10000*(1/(10000*(1-TBM(X(8),X(24)))+1))
599 T(199)=5*10000*(1/(10000*(1-TBM(X(8),X(25)))+1))
600 T(200)=0*10000*(1/(10000*(1-TBM(X(8),X(26)))+1))
601 T(201)=5*10000*(1/(10000*(1-TBM(X(8),X(27)))+1))
602 T(202)=5*10000*(1/(10000*(1-TBM(X(8),X(28)))+1))
603 T(203)=0*10000*(1/(10000*(1-TBM(X(8),X(29)))+1))
604 T(204)=2*10000*(1/(10000*(1-TBM(X(8),X(30)))+1))
605 T(205)=10*10000*(1/(10000*(1-TBM(X(9),X(10)))+1))
606 T(206)=2*10000*(1/(10000*(1-TBM(X(9),X(11)))+1))
607 T(207)=1*10000*(1/(10000*(1-TBM(X(9),X(12)))+1))
608 T(208)=5*10000*(1/(10000*(1-TBM(X(9),X(13)))+1))
609 T(209)=2*10000*(1/(10000*(1-TBM(X(9),X(14)))+1))
610 T(210)=0*10000*(1/(10000*(1-TBM(X(9),X(15)))+1))
611 T(211)=3*10000*(1/(10000*(1-TBM(X(9),X(16)))+1))
612 T(212)=0*10000*(1/(10000*(1-TBM(X(9),X(17)))+1))
613 T(213)=2*10000*(1/(10000*(1-TBM(X(9),X(18)))+1))
614 T(214)=0*10000*(1/(10000*(1-TBM(X(9),X(19)))+1))
615 T(215)=0*10000*(1/(10000*(1-TBM(X(9),X(20)))+1))
616 T(216)=4*10000*(1/(10000*(1-TBM(X(9),X(21)))+1))
617 T(217)=0*10000*(1/(10000*(1-TBM(X(9),X(22)))+1))
618 T(218)=5*10000*(1/(10000*(1-TBM(X(9),X(23)))+1))
619 T(219)=2*10000*(1/(10000*(1-TBM(X(9),X(24)))+1))
620 T(220)=0*10000*(1/(10000*(1-TBM(X(9),X(25)))+1))
621 T(221)=5*10000*(1/(10000*(1-TBM(X(9),X(26)))+1))
622 T(222)=2*10000*(1/(10000*(1-TBM(X(9),X(27)))+1))
623 T(223)=2*10000*(1/(10000*(1-TBM(X(9),X(28)))+1))
624 T(224)=5*10000*(1/(10000*(1-TBM(X(9),X(29)))+1))
625 T(225)=2*10000*(1/(10000*(1-TBM(X(9),X(30)))+1))
626 T(226)=5*10000*(1/(10000*(1-TBM(X(10),X(11)))+1))
627 T(227)=5*10000*(1/(10000*(1-TBM(X(10),X(12)))+1))
628 T(228)=6*10000*(1/(10000*(1-TBM(X(10),X(13)))+1))
629 T(229)=0*10000*(1/(10000*(1-TBM(X(10),X(14)))+1))
630 T(230)=1*10000*(1/(10000*(1-TBM(X(10),X(15)))+1))
631 T(231)=5*10000*(1/(10000*(1-TBM(X(10),X(16)))+1))
632 T(232)=5*10000*(1/(10000*(1-TBM(X(10),X(17)))+1))
633 T(233)=0*10000*(1/(10000*(1-TBM(X(10),X(18)))+1))
634 T(234)=5*10000*(1/(10000*(1-TBM(X(10),X(19)))+1))
635 T(235)=2*10000*(1/(10000*(1-TBM(X(10),X(20)))+1))
636 T(236)=3*10000*(1/(10000*(1-TBM(X(10),X(21)))+1))
637 T(237)=5*10000*(1/(10000*(1-TBM(X(10),X(22)))+1))
638 T(238)=0*10000*(1/(10000*(1-TBM(X(10),X(23)))+1))
639 T(239)=5*10000*(1/(10000*(1-TBM(X(10),X(24)))+1))
640 T(240)=2*10000*(1/(10000*(1-TBM(X(10),X(25)))+1))
641 T(241)=10*10000*(1/(10000*(1-TBM(X(10),X(26)))+1))
642 T(242)=10*10000*(1/(10000*(1-TBM(X(10),X(27)))+1))
643 T(243)=1*10000*(1/(10000*(1-TBM(X(10),X(28)))+1))
644 T(244)=5*10000*(1/(10000*(1-TBM(X(10),X(29)))+1))
645 T(245)=2*10000*(1/(10000*(1-TBM(X(10),X(30)))+1))
646 T(246)=0*10000*(1/(10000*(1-TBM(X(11),X(12)))+1))
647 T(247)=0*10000*(1/(10000*(1-TBM(X(11),X(13)))+1))
648 T(248)=1*10000*(1/(10000*(1-TBM(X(11),X(14)))+1))
649 T(249)=2*10000*(1/(10000*(1-TBM(X(11),X(15)))+1))
650 T(250)=1*10000*(1/(10000*(1-TBM(X(11),X(16)))+1))
651 T(251)=0*10000*(1/(10000*(1-TBM(X(11),X(17)))+1))
652 T(252)=2*10000*(1/(10000*(1-TBM(X(11),X(18)))+1))
653 T(253)=0*10000*(1/(10000*(1-TBM(X(11),X(19)))+1))
654 T(254)=0*10000*(1/(10000*(1-TBM(X(11),X(20)))+1))
655 T(255)=0*10000*(1/(10000*(1-TBM(X(11),X(21)))+1))
656 T(256)=6*10000*(1/(10000*(1-TBM(X(11),X(22)))+1))
657 T(257)=6*10000*(1/(10000*(1-TBM(X(11),X(23)))+1))
658 T(258)=0*10000*(1/(10000*(1-TBM(X(11),X(24)))+1))
659 T(259)=4*10000*(1/(10000*(1-TBM(X(11),X(25)))+1))
660 T(260)=5*10000*(1/(10000*(1-TBM(X(11),X(26)))+1))
661 T(261)=3*10000*(1/(10000*(1-TBM(X(11),X(27)))+1))
662 T(262)=2*10000*(1/(10000*(1-TBM(X(11),X(28)))+1))
663 T(263)=2*10000*(1/(10000*(1-TBM(X(11),X(29)))+1))
664 T(264)=10*10000*(1/(10000*(1-TBM(X(11),X(30)))+1))
665 T(265)=5*10000*(1/(10000*(1-TBM(X(12),X(13)))+1))
666 T(266)=5*10000*(1/(10000*(1-TBM(X(12),X(14)))+1))
667 T(267)=2*10000*(1/(10000*(1-TBM(X(12),X(15)))+1))
668 T(268)=0*10000*(1/(10000*(1-TBM(X(12),X(16)))+1))
669 T(269)=0*10000*(1/(10000*(1-TBM(X(12),X(17)))+1))
670 T(270)=0*10000*(1/(10000*(1-TBM(X(12),X(18)))+1))
671 T(271)=0*10000*(1/(10000*(1-TBM(X(12),X(19)))+1))
672 T(272)=2*10000*(1/(10000*(1-TBM(X(12),X(20)))+1))
673 T(273)=0*10000*(1/(10000*(1-TBM(X(12),X(21)))+1))
674 T(274)=4*10000*(1/(10000*(1-TBM(X(12),X(22)))+1))
675 T(275)=5*10000*(1/(10000*(1-TBM(X(12),X(23)))+1))
676 T(276)=10*10000*(1/(10000*(1-TBM(X(12),X(24)))+1))
677 T(277)=1*10000*(1/(10000*(1-TBM(X(12),X(25)))+1))
678 T(278)=0*10000*(1/(10000*(1-TBM(X(12),X(26)))+1))
679 T(279)=0*10000*(1/(10000*(1-TBM(X(12),X(27)))+1))
680 T(280)=0*10000*(1/(10000*(1-TBM(X(12),X(28)))+1))
681 T(281)=0*10000*(1/(10000*(1-TBM(X(12),X(29)))+1))
682 T(282)=1*10000*(1/(10000*(1-TBM(X(12),X(30)))+1))
683 T(283)=2*10000*(1/(10000*(1-TBM(X(13),X(14)))+1))
684 T(284)=0*10000*(1/(10000*(1-TBM(X(13),X(15)))+1))
685 T(285)=4*10000*(1/(10000*(1-TBM(X(13),X(16)))+1))
686 T(286)=2*10000*(1/(10000*(1-TBM(X(13),X(17)))+1))
687 T(287)=2*10000*(1/(10000*(1-TBM(X(13),X(18)))+1))
688 T(288)=1*10000*(1/(10000*(1-TBM(X(13),X(19)))+1))
689 T(289)=0*10000*(1/(10000*(1-TBM(X(13),X(20)))+1))
690 T(290)=6*10000*(1/(10000*(1-TBM(X(13),X(21)))+1))
691 T(291)=2*10000*(1/(10000*(1-TBM(X(13),X(22)))+1))
692 T(292)=1*10000*(1/(10000*(1-TBM(X(13),X(23)))+1))
693 T(293)=5*10000*(1/(10000*(1-TBM(X(13),X(24)))+1))
694 T(294)=5*10000*(1/(10000*(1-TBM(X(13),X(25)))+1))
695 T(295)=0*10000*(1/(10000*(1-TBM(X(13),X(26)))+1))
696 T(296)=0*10000*(1/(10000*(1-TBM(X(13),X(27)))+1))
697 T(297)=1*10000*(1/(10000*(1-TBM(X(13),X(28)))+1))
698 T(298)=5*10000*(1/(10000*(1-TBM(X(13),X(29)))+1))
699 T(299)=5*10000*(1/(10000*(1-TBM(X(13),X(30)))+1))
700 T(300)=2*10000*(1/(10000*(1-TBM(X(14),X(15)))+1))
701 T(301)=1*10000*(1/(10000*(1-TBM(X(14),X(16)))+1))
702 T(302)=0*10000*(1/(10000*(1-TBM(X(14),X(17)))+1))
703 T(303)=5*10000*(1/(10000*(1-TBM(X(14),X(18)))+1))
704 T(304)=3*10000*(1/(10000*(1-TBM(X(14),X(19)))+1))
705 T(305)=10*10000*(1/(10000*(1-TBM(X(14),X(20)))+1))
706 T(306)=0*10000*(1/(10000*(1-TBM(X(14),X(21)))+1))
707 T(307)=0*10000*(1/(10000*(1-TBM(X(14),X(22)))+1))
708 T(308)=4*10000*(1/(10000*(1-TBM(X(14),X(23)))+1))
709 T(309)=2*10000*(1/(10000*(1-TBM(X(14),X(24)))+1))
710 T(310)=0*10000*(1/(10000*(1-TBM(X(14),X(25)))+1))
711 T(311)=0*10000*(1/(10000*(1-TBM(X(14),X(26)))+1))
712 T(312)=4*10000*(1/(10000*(1-TBM(X(14),X(27)))+1))
713 T(313)=2*10000*(1/(10000*(1-TBM(X(14),X(28)))+1))
714 T(314)=5*10000*(1/(10000*(1-TBM(X(14),X(29)))+1))
715 T(315)=5*10000*(1/(10000*(1-TBM(X(14),X(30)))+1))
716 T(316)=4*10000*(1/(10000*(1-TBM(X(15),X(16)))+1))
717 T(317)=5*10000*(1/(10000*(1-TBM(X(15),X(17)))+1))
718 T(318)=1*10000*(1/(10000*(1-TBM(X(15),X(18)))+1))
719 T(319)=0*10000*(1/(10000*(1-TBM(X(15),X(19)))+1))
720 T(320)=1*10000*(1/(10000*(1-TBM(X(15),X(20)))+1))
721 T(321)=0*10000*(1/(10000*(1-TBM(X(15),X(21)))+1))
722 T(322)=5*10000*(1/(10000*(1-TBM(X(15),X(22)))+1))
723 T(323)=0*10000*(1/(10000*(1-TBM(X(15),X(23)))+1))
724 T(324)=2*10000*(1/(10000*(1-TBM(X(15),X(24)))+1))
725 T(325)=0*10000*(1/(10000*(1-TBM(X(15),X(25)))+1))
726 T(326)=0*10000*(1/(10000*(1-TBM(X(15),X(26)))+1))
727 T(327)=5*10000*(1/(10000*(1-TBM(X(15),X(27)))+1))
728 T(328)=1*10000*(1/(10000*(1-TBM(X(15),X(28)))+1))
729 T(329)=1*10000*(1/(10000*(1-TBM(X(15),X(29)))+1))
730 T(330)=0*10000*(1/(10000*(1-TBM(X(15),X(30)))+1))
731 T(331)=0*10000*(1/(10000*(1-TBM(X(16),X(17)))+1))
732 T(332)=3*10000*(1/(10000*(1-TBM(X(16),X(18)))+1))
733 T(333)=0*10000*(1/(10000*(1-TBM(X(16),X(19)))+1))
734 T(334)=2*10000*(1/(10000*(1-TBM(X(16),X(20)))+1))
735 T(335)=2*10000*(1/(10000*(1-TBM(X(16),X(21)))+1))
736 T(336)=0*10000*(1/(10000*(1-TBM(X(16),X(22)))+1))
737 T(337)=2*10000*(1/(10000*(1-TBM(X(16),X(23)))+1))
738 T(338)=0*10000*(1/(10000*(1-TBM(X(16),X(24)))+1))
739 T(339)=5*10000*(1/(10000*(1-TBM(X(16),X(25)))+1))
740 T(340)=0*10000*(1/(10000*(1-TBM(X(16),X(26)))+1))
741 T(341)=5*10000*(1/(10000*(1-TBM(X(16),X(27)))+1))
742 T(342)=2*10000*(1/(10000*(1-TBM(X(16),X(28)))+1))
743 T(343)=5*10000*(1/(10000*(1-TBM(X(16),X(29)))+1))
744 T(344)=10*10000*(1/(10000*(1-TBM(X(16),X(30)))+1))
745 T(345)=2*10000*(1/(10000*(1-TBM(X(17),X(18)))+1))
746 T(346)=2*10000*(1/(10000*(1-TBM(X(17),X(19)))+1))
747 T(347)=0*10000*(1/(10000*(1-TBM(X(17),X(20)))+1))
748 T(348)=0*10000*(1/(10000*(1-TBM(X(17),X(21)))+1))
749 T(349)=0*10000*(1/(10000*(1-TBM(X(17),X(22)))+1))
750 T(350)=6*10000*(1/(10000*(1-TBM(X(17),X(23)))+1))
751 T(351)=5*10000*(1/(10000*(1-TBM(X(17),X(24)))+1))
752 T(352)=3*10000*(1/(10000*(1-TBM(X(17),X(25)))+1))
753 T(353)=5*10000*(1/(10000*(1-TBM(X(17),X(26)))+1))
754 T(354)=0*10000*(1/(10000*(1-TBM(X(17),X(27)))+1))
755 T(355)=0*10000*(1/(10000*(1-TBM(X(17),X(28)))+1))
756 T(356)=5*10000*(1/(10000*(1-TBM(X(17),X(29)))+1))
757 T(357)=1*10000*(1/(10000*(1-TBM(X(17),X(30)))+1))
758 T(358)=5*10000*(1/(10000*(1-TBM(X(18),X(19)))+1))
759 T(359)=1*10000*(1/(10000*(1-TBM(X(18),X(20)))+1))
760 T(360)=2*10000*(1/(10000*(1-TBM(X(18),X(21)))+1))
761 T(361)=10*10000*(1/(10000*(1-TBM(X(18),X(22)))+1))
762 T(362)=10*10000*(1/(10000*(1-TBM(X(18),X(23)))+1))
763 T(363)=4*10000*(1/(10000*(1-TBM(X(18),X(24)))+1))
764 T(364)=0*10000*(1/(10000*(1-TBM(X(18),X(25)))+1))
765 T(365)=0*10000*(1/(10000*(1-TBM(X(18),X(26)))+1))
766 T(366)=5*10000*(1/(10000*(1-TBM(X(18),X(27)))+1))
767 T(367)=0*10000*(1/(10000*(1-TBM(X(18),X(28)))+1))
768 T(368)=0*10000*(1/(10000*(1-TBM(X(18),X(29)))+1))
769 T(369)=0*10000*(1/(10000*(1-TBM(X(18),X(30)))+1))
770 T(370)=0*10000*(1/(10000*(1-TBM(X(19),X(20)))+1))
771 T(371)=5*10000*(1/(10000*(1-TBM(X(19),X(21)))+1))
772 T(372)=5*10000*(1/(10000*(1-TBM(X(19),X(22)))+1))
773 T(373)=1*10000*(1/(10000*(1-TBM(X(19),X(23)))+1))
774 T(374)=0*10000*(1/(10000*(1-TBM(X(19),X(24)))+1))
775 T(375)=5*10000*(1/(10000*(1-TBM(X(19),X(25)))+1))
776 T(376)=2*10000*(1/(10000*(1-TBM(X(19),X(26)))+1))
777 T(377)=1*10000*(1/(10000*(1-TBM(X(19),X(27)))+1))
778 T(378)=2*10000*(1/(10000*(1-TBM(X(19),X(28)))+1))
779 T(379)=10*10000*(1/(10000*(1-TBM(X(19),X(29)))+1))
780 T(380)=10*10000*(1/(10000*(1-TBM(X(19),X(30)))+1))
781 T(381)=5*10000*(1/(10000*(1-TBM(X(20),X(21)))+1))
782 T(382)=2*10000*(1/(10000*(1-TBM(X(20),X(22)))+1))
783 T(383)=1*10000*(1/(10000*(1-TBM(X(20),X(23)))+1))
784 T(384)=3*10000*(1/(10000*(1-TBM(X(20),X(24)))+1))
785 T(385)=1*10000*(1/(10000*(1-TBM(X(20),X(25)))+1))
786 T(386)=5*10000*(1/(10000*(1-TBM(X(20),X(26)))+1))
787 T(387)=6*10000*(1/(10000*(1-TBM(X(20),X(27)))+1))
788 T(388)=5*10000*(1/(10000*(1-TBM(X(20),X(28)))+1))
789 T(389)=5*10000*(1/(10000*(1-TBM(X(20),X(29)))+1))
790 T(390)=3*10000*(1/(10000*(1-TBM(X(20),X(30)))+1))
791 T(391)=4*10000*(1/(10000*(1-TBM(X(21),X(22)))+1))
792 T(392)=0*10000*(1/(10000*(1-TBM(X(21),X(23)))+1))
793 T(393)=1*10000*(1/(10000*(1-TBM(X(21),X(24)))+1))
794 T(394)=0*10000*(1/(10000*(1-TBM(X(21),X(25)))+1))
795 T(395)=0*10000*(1/(10000*(1-TBM(X(21),X(26)))+1))
796 T(396)=0*10000*(1/(10000*(1-TBM(X(21),X(27)))+1))
797 T(397)=5*10000*(1/(10000*(1-TBM(X(21),X(28)))+1))
798 T(398)=0*10000*(1/(10000*(1-TBM(X(21),X(29)))+1))
799 T(399)=0*10000*(1/(10000*(1-TBM(X(21),X(30)))+1))
800 T(400)=5*10000*(1/(10000*(1-TBM(X(22),X(23)))+1))
801 T(401)=0*10000*(1/(10000*(1-TBM(X(22),X(24)))+1))
802 T(402)=4*10000*(1/(10000*(1-TBM(X(22),X(25)))+1))
803 T(403)=4*10000*(1/(10000*(1-TBM(X(22),X(26)))+1))
804 T(404)=5*10000*(1/(10000*(1-TBM(X(22),X(27)))+1))
805 T(405)=0*10000*(1/(10000*(1-TBM(X(22),X(28)))+1))
806 T(406)=2*10000*(1/(10000*(1-TBM(X(22),X(29)))+1))
807 T(407)=5*10000*(1/(10000*(1-TBM(X(22),X(30)))+1))
808 T(408)=0*10000*(1/(10000*(1-TBM(X(23),X(24)))+1))
809 T(409)=4*10000*(1/(10000*(1-TBM(X(23),X(25)))+1))
810 T(410)=4*10000*(1/(10000*(1-TBM(X(23),X(26)))+1))
811 T(411)=1*10000*(1/(10000*(1-TBM(X(23),X(27)))+1))
812 T(412)=0*10000*(1/(10000*(1-TBM(X(23),X(28)))+1))
813 T(413)=2*10000*(1/(10000*(1-TBM(X(23),X(29)))+1))
814 T(414)=2*10000*(1/(10000*(1-TBM(X(23),X(30)))+1))
815 T(415)=5*10000*(1/(10000*(1-TBM(X(24),X(25)))+1))
816 T(416)=5*10000*(1/(10000*(1-TBM(X(24),X(26)))+1))
817 T(417)=0*10000*(1/(10000*(1-TBM(X(24),X(27)))+1))
818 T(418)=1*10000*(1/(10000*(1-TBM(X(24),X(28)))+1))
819 T(419)=0*10000*(1/(10000*(1-TBM(X(24),X(29)))+1))
820 T(420)=0*10000*(1/(10000*(1-TBM(X(24),X(30)))+1))
821 T(421)=1*10000*(1/(10000*(1-TBM(X(25),X(26)))+1))
822 T(422)=0*10000*(1/(10000*(1-TBM(X(25),X(27)))+1))
823 T(423)=10*10000*(1/(10000*(1-TBM(X(25),X(28)))+1))
824 T(424)=1*10000*(1/(10000*(1-TBM(X(25),X(29)))+1))
825 T(425)=0*10000*(1/(10000*(1-TBM(X(25),X(30)))+1))
826 T(426)=0*10000*(1/(10000*(1-TBM(X(26),X(27)))+1))
827 T(427)=0*10000*(1/(10000*(1-TBM(X(26),X(28)))+1))
828 T(428)=0*10000*(1/(10000*(1-TBM(X(26),X(29)))+1))
829 T(429)=0*10000*(1/(10000*(1-TBM(X(26),X(30)))+1))
830 T(430)=0*10000*(1/(10000*(1-TBM(X(27),X(28)))+1))
831 T(431)=0*10000*(1/(10000*(1-TBM(X(27),X(29)))+1))
832 T(432)=10*10000*(1/(10000*(1-TBM(X(27),X(30)))+1))
833 T(433)=2*10000*(1/(10000*(1-TBM(X(28),X(29)))+1))
834 T(434)=2*10000*(1/(10000*(1-TBM(X(28),X(30)))+1))
835 T(435)=2*10000*(1/(10000*(1-TBM(X(29),X(30)))+1))
1151 P1NEW=0
1152 FOR KAU7=1 TO 435
1153 P1NEW=P1NEW+T(KAU7)
1154 NEXT KAU7
1450 P=-P1NEW
1451 IF P<=M THEN 1670
1657 FOR KEW=1 TO 30
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 PP1=P1NEW
1666 GOTO 128
1670 NEXT I
1890 IF M>-1500000! THEN 1941 ELSE 1999
1941 PRINT A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9),A(10)
1942 PRINT A(11),A(12),A(13),A(14),A(15),A(16),A(17),A(18),A(19),A(20)
1943 PRINT A(21),A(22),A(23),A(24),A(25),A(26),A(27),A(28),A(29),A(30)
1951 PRINT JJJJ,M,IMAR
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and some of the best candidate solutions (in compressed form and to be interpreted in accordance with line 1941 through line 1951) from the first twenty minutes of running is presented below.
3 1 1 1 3
1 1 1 3 1
3 3 3 1 3
4 4 3 3 3
4 4 4 5 6
6 5 5 5 6
-31946 -1370972 1186
3 1 1 1 3
1 1 1 3 1
3 3 3 1 3
4 4 3 3 3
4 4 4 5 6
6 5 5 5 6
-31855 -1370972 1174
3 1 1 1 3
1 1 1 3 1
3 3 3 1 3
4 4 3 3 3
4 4 4 5 6
6 5 5 5 6
-31778 -1370972 376
In summmary, the candidate solution above occurred at JJJJ=-31946, -31855, -31778, -31762, -31759, -31725, -31702, -31685, -31663, -31634, -31626, and -31599 during the first twenty minutes of running on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter.
The candidate solution indicates that courses 2, 3, 4, 6, 7, 8, 10, and 14 are assigned to time block 1; the other courses are assigned similarly. Then the conflict cost is 137.
Thus the conflict cost of 137 occurred twelve times during the first twenty minutes of running the program above. If one makes changes to the computer program, such as a change of changing line 111 above to, for example, 111 IMAR=50+FIX(RND*3000), one may or may not obtain this conflict cost of 137, which may or may not be the minimum. This point is relevant to the present problem AND beyond it. That leads to a general remedy that in general, in order to increase the chance of getting an optimal solution, one preferably should run several computers simultaneously, each with a different line 111. Running several computers simultaneously can mitigate the possible danger of missing optimality. Also, one should look into other algorithms for solving the problem [1, 2, and 3].
One future research direction is to use the computer program listed above as a model for problems of similar nature. In particular, it is worthy of note that one way to handle the objective function on page 225 of Davis et al. [2] is to use lines similar to line 401 of the computer program above. Perhaps there are other uses of lines similar to line 401.
References
[1] R. C. Carlson and G. L. Nemhauser, "Scheduling To Minimize Interaction Cost," Operations Research, 14, 52-58 (1966).
[2] F. E. Davis, M. D. Devine, and R. P. Lutz, "Scheduling Activities among Conflicting Facilities To Minimize Conflict Cost," Mathematical Programming, 6, 224-228 (1974).
[3] R. P. Lutz, M. D.Devine, H. J. Kumin, and W. C. Smith, "An Application of Operations Research to School Desegregation," Management Science, 19, No. 4, 100-109.
[4] C. E. Nugent, T. E. Vollmann, and J. Ruml, "An Experimental Comparison of Techniques for Assignment of Facilities to Locations," Operations Research, 16, 150-173 (1968).
Sunday, April 6, 2008
Thursday, February 28, 2008
Subscribe to:
Posts (Atom)