The computer program listed here is concerned with a problem of scheduling activities among conflicting facilities to minimize conflict cost, which arises when two activities are assigned to the same facility or to two facilities operating in conflict. The problem is a generalization of the original Carlson and Nemhauser problem to minimize interaction cost [1], which arises when, for example, two courses are scheduled during the same time period. Basically, 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.].
The computer program below illustrates a discrete optimizing algorithm with a case of assigning 30 courses (activities) to 6 time blocks (facilities) to minimize total conflict cost, given the interdepartmental flows of the Nug30 problem as the conflict costs of all pairs of courses [5, 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 through 3, courses 15 through 23 may be assigned in time blocks 2 through 4, and courses 24 through 30 may be assigned to time blocks 4 through 6. The computer program and its output are presented below.
2 DEFINT I,J,K
3 DIM TBM(6,6)
7 DIM A(99),X(99),T(500),Z(99)
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
42 FOR JJJJ=-32000 TO 32000
44 RANDOMIZE JJJJ
46 M=-1D+17
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
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
1658 A(KEW)=X(KEW)
1659 NEXT KEW
1661 M=P
1662 PP1=P1NEW
1670 NEXT I
1890 IF M>-1390000! 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
1999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and the program's best output (in compressed form and to be interpreted in accordance with line 1941 through line 1951) for JJJJ=-32000 through JJJJ=-31776 is as follows:
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 6 5 6 5
-31999 -1380971
1 3 3 3 1
3 3 1 1 3
1 1 1 1 3
4 4 4 4 3
4 4 3 6 5
5 6 6 6 5
-31969 -1380971
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
-31923 -1370972
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
-31886 -1370972
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
-31872 -1370972
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
-31835 -1370972
3 1 1 1 3
1 1 1 3 1
3 3 3 1 3
4 4 3 3 3
4 4 4 6 5
5 6 6 6 5
-31776 -1370972
(There are additional solutions with the conflict cost of 138 between JJJJ=-32000 and JJJJ=-31776.)
These computational results were produced in 6 minutes on a personal computer with an Intel 2.66 GHz. chip and the IBM interpreter. The candidate solution above at JJJJ=-31923 indicates that courses 2, 3, 4, 6, 7, 8, 10, and 14 are scheduled during time block 1; the other courses are assigned similarly. Then the conflict cost is 137.
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 expressions similar to expression 401 of the computer program above. Perhaps there are other uses for expressions similar to expression 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] J. A. Ferland and S. Roy, "Timetabling Problem for University as Assignment of Activities to Resources," Computers and Operations Resourch, 12, 207-218 (1985).
[4] 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.
[5] 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).
