The following computer program seeks to schedule 40 two-hour lectures between 7 a.m. and 7 p.m. This problem is based on Carlson and Nemhauser [9]; the interaction costs of line 42 through line 87 are from Anjos [6; see the data for instance Am_2009_33dept_set3 and for instance srflp.40].
While line 126 and line 128 of the two immediately preceding papers are
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 1500
and
126 REM IMAR=10+FIX(RND*1000)
128 FOR I=1 TO 500, respectively,
line 126 and line 128 here are
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR.
Two interesting references to this problem are Davis, Devine, and Lutz [14] and Vredeveld and Lenstra [38].
0 REM DEFDBL A-Z
1 DEFINT A-Z
2 DIM B(99),N(99),A(2002),H(99),L(99),U(99),X(2002),D(111),P(111),PS(33),J44(2002),J(99),AA(99),HR(32),HHR(32)
3 DIM HS(40,40),HHS(40,40)
4 DIM PE(49,49)
5 DIM SD(49,49)
31 FOR IL=1 TO 39
32 FOR JL=IL+1 TO 40
33 READ HS(IL,JL)
34 NEXT JL
35 NEXT IL
42 DATA 3,2,0,0,2,10,5,0,5,2,5,0,0,2,0,5,6,3,0,1,10,0,10,2,1,1,1,0,1,0,6,2, 0,8,5,0,10,1,0
43 DATA 4,0,10,4,0,0,2,2,1,0,5,0,0,0,0,2,0,1,6,1,0,1,2,2,5,1,10,5,3,1,3, 0,0,9,3,6,0,0
44 DATA 3,4,0,5,5,5,1,4,1,0,4,0,4,0,6,3,2,5,5,2,1,0,0,3,1,0,2,6,1,0, 0,0,0,0,10,8,0
45 DATA 0,0,0,2,2,0,6,0,2,5,2,5,1,1,1,1,2,2,4,0,2,0,2,2,5,5,3,0,2, 8,5,0,6,5,0,0
46 DATA 5,2,0,0,0,0,2,0,0,0,0,2,1,0,0,2,0,5,1,0,2,1,0,2,1,0,1,3, 2,0,2,9,8,6,1
47 DATA 1,2,2,1,4,10,10,2,5,5,0,5,0,0,0,10,0,0,0,4,0,10,1,1,2,0,6, 10,0,4,9,2,9,0
48 DATA 10,10,5,10,10,6,0,0,10,2,1,10,1,5,5,2,3,5,0,2,0,1,3,0,10,2, 8,5,0,0,0,7,0
49 DATA 1,3,5,0,0,0,2,4,5,2,10,6,0,5,5,2,5,0,5,5,0,2,6,3,0, 2,6,4,1,0,0,5
50 DATA 10,2,1,5,2,0,3,0,2,0,0,4,0,5,2,0,5,2,2,5,2,0,6,1, 0,0,1,0,0,6,0
51 DATA 5,5,6,0,1,5,5,0,5,2,3,5,0,5,2,10,10,1,5,2,0,10,0, 2,8,3,1,0,8,10
52 DATA 0,0,1,2,1,0,2,0,0,0,6,6,0,4,5,3,2,2,10,3,0,5, 2,6,4,0,7,0,0
53 DATA 5,5,2,0,0,0,0,2,0,4,5,10,1,0,0,0,0,1,3,3,1, 0,0,5,0,0,0,1
54 DATA 2,0,4,2,2,1,0,6,2,1,5,5,0,0,1,5,5,3,3,2, 9,0,6,0,0,9,9
55 DATA 2,1,0,5,3,10,0,0,4,2,0,0,4,2,5,5,2,3,1, 0,6,7,8,4,5,0
56 DATA 4,5,1,0,1,0,5,0,2,0,0,5,1,1,0,3,1,0, 10,0,0,9,0,0,10
57 DATA 0,3,0,2,2,0,2,0,5,0,5,2,5,10,5,0,3, 0,0,2,4,7,6,10
58 DATA 2,2,0,0,0,6,5,3,5,0,0,5,1,0,4,2, 9,10,3,0,7,5,0
59 DATA 5,1,2,10,10,4,0,0,5,0,0,0,3,2,3, 0,9,0,0,9,0,0
60 DATA 0,5,5,1,0,5,2,1,2,10,10,3,5,0, 0,0,4,0,4,1,0
61 DATA 5,2,1,3,1,5,6,5,5,3,0,3,3, 0,0,2,0,3,10,5
62 DATA 4,0,1,0,0,0,5,0,0,5,1,0, 5,0,0,0,5,9,2
63 DATA 5,0,4,4,5,0,2,5,1,0,10, 0,0,7,4,10,3,0
64 DATA 0,4,4,1,0,2,2,6,2,0, 0,0,6,0,1,6,0
65 DATA 5,5,0,1,0,0,4,3,0, 5,9,0,0,10,3,0
66 DATA 1,0,10,1,0,2,2,3, 0,0,4,10,9,4,3
67 DATA 0,0,0,0,3,0,2, 1,5,0,0,0,0,0
68 DATA 0,0,10,5,3,0, 7,0,8,4,0,4,9
69 DATA 2,2,3,0,3, 0,10,3,0,0,5,10
70 DATA 2,5,0,3, 1,6,6,7,9,0,0
73 DATA 3,6,0, 3,8,8,5,3,8,0
74 DATA 2,3, 2,0,2,0,9,0,0
75 DATA 3, 2,0,4,5,1,0,0
81 DATA 0,0,0,0,0,1,0
82 DATA 10,0,0,6,8,9
83 DATA 0,10,0,0,0
84 DATA 0,9,0,0
85 DATA 3,0,3
86 DATA 8,10
87 DATA 0
88 FOR JJJJ=-32000 TO 32000
89 RANDOMIZE JJJJ
90 M=-32222
91 FOR J44=1 TO 40
93 A(J44)=1+FIX(RND*6)
94 NEXT J44
126 IMAR=10+FIX(RND*1500)
128 FOR I=1 TO IMAR
129 FOR KKQQ=1 TO 40
130 X(KKQQ)=A(KKQQ)
131 NEXT KKQQ
133 REM III=1+FIX(RND*30)
134 REM JJJ=1+FIX(RND*30)
221 REM X(III)=A(JJJ)
223 REM X(JJJ)=A(III)
224 X(1+FIX(RND*40) ) =1+FIX(RND*6)
225 FOR II=1 TO 39
227 FOR JJ=II+1 TO 40
256 IF X(II)=X(JJ) THEN HHS(II,JJ)=HS(II,JJ) ELSE HHS(II,JJ)=0
267 NEXT JJ
271 NEXT II
305 PDU=0
309 FOR IW=1 TO 39
312 FOR J88=IW+1 TO 40
318 PDU=PDU-HHS(IW,J88)
320 NEXT J88
321 NEXT IW
359 POB1=PDU
444 P1NEWMAY=POB1
466 P=P1NEWMAY
1111 IF P<=M THEN 1670
1452 M=P
1454 FOR KLX=1 TO 40
1455 A(KLX)=X(KLX)
1456 NEXT KLX
1557 GOTO 128
1670 NEXT I
1889 IF M<-70 THEN 1999
1901 PRINT A(1),A(2),A(3),A(4),A(5)
1902 PRINT A(6),A(7),A(8),A(9),A(10)
1903 PRINT A(11),A(12),A(13),A(14),A(15)
1904 PRINT A(16),A(17),A(18),A(19),A(20)
1905 PRINT A(21),A(22),A(23),A(24),A(25)
1906 PRINT A(26),A(27),A(28),A(29),A(30)
1907 PRINT A(31),A(32),A(33),A(34),A(35)
1908 PRINT A(36),A(37),A(38),A(39),A(40)
1917 PRINT M,JJJJ
1999 NEXT JJJJ
This BASIC computer program was run via basica/D of Microsoft's GW-BASIC 3.11 interpreter. The top-three candidate solutions through JJJJ=-27544 are shown below. What follows is a hand copy from the computer-monitor screen; immediately below there is no rounding by hand.
5 1 4 4 2
4 4 3 5 2
5 3 6 1 2
1 1 2 5 5
2 1 6 4 2
3 6 1 3 2
5 3 6 5 6
4 5 6 3 4
-67 -30275
6 2 3 3 4
3 3 5 6 4
6 5 1 2 4
2 2 5 6 6
4 2 1 3 4
5 1 2 5 4
6 2 1 6 1
3 6 1 5 3
-67 -27627
1 5 6 6 4
6 6 2 1 4
1 2 3 5 4
5 5 2 1 1
4 5 3 6 4
2 3 5 2 4
1 5 3 1 3
6 1 3 2 6
-67 -27544
On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM, and the IBM basica/D interpreter, version GW BASIC 3.11, the wall-clock time from JJJJ=-32000 through JJJJ=-27544 was five hours.
References
[1] Andre R. S. Amaral (2006), On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research 173 (2006), pp. 508-518.
[2] Andre R. S. Amaral (2008), An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, Vol. 56, No. 4 (July-August, 2008), pp. 1026-1033.
[3] Andre R. S. Amaral (2011), Optimal Solutions for the Double Row Layout Problem. Optimization Letters, DOI 10.1007/s11590-011-0426-8, published on line 30 November 2011, Springer-Verlag 2011.
[4] Andre R. S. Amaral (2012), The Corridor Allocation Problem. Computers and Operations Research 39 (2012), pp. 3325-3330.
[5] Miguel F. Anjos, Anthony Vannelli, Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, Vol. 20, No. 4, Fall 2008, pp. 611-617.
[6] Miguel F. Anjos (2012), FLPLIB--Facility Layout Database. Retrieved on September 25 2012 from www.gerad.ca/files/Sites/Anjos/indexFR.html
[7] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton and Oxford: Princeton University Press, 2006.
[8] L. L. Barachet (1957), Graphic Solution of the Travelling Salesman Problem. Operations Research. Vol. 5, pp. 841-845.
[9] R. C. Carlson and G. L. Nemhauser, Scheduling To Minimize Interaction Cost. Operations Research, Vol. 14, No. 1 (Jan. - Feb., 1966), pp. 52-58.
[10] T. Y. Chen, H. C. Chen (2009), Mixed-Discrete Structural Optimization Using a Rank-Niche Evolution Strategy, Engineering Optimization, 41:1, 39-58.
[11] Leon Cooper, U. N. Bhat, L. J. LeBlanc, Introduction to Operations Research Models. W. B. Saunders Company, 1977.
[12] George B. Dantzig, Discrete-Variable Extremum Problems. Operations Research, Vol. 5, No. 2 (Apr., 1957), pp. 266-277.
[13] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large-Scale Traveling-Salesman Problem.
Operations Research, Vol. 2, No. 4 (Nov., 1954), pp. 393-410.
[14] F. E. Davis, M. D. Devine, and R. P. Lutz, Scheduling Activities Among Conflicting Facilities To Minimize Conflict Cost. Mathematical Programming 6 (1974) 224-228)
[15] Zvi Drezner (1980), DISCON: A New Method for the Layout Problem. Operations Research, Vol. 28, No. 6 (Nov. - Dec., 1980), pp. 1375-1384.
[16] W. J. Fabrycky, P. M. Ghare, P. E. Torgersen, Applied Operations Research and Management Science. Englewood Cliffs, N. J. 07362: Prentice-Hall, Inc., 1984.
[17] Billy E. Gillett, Introduction to Operations Research: A Computer-Oriented Algorithmic Approach. McGraw-Hill, Inc., 1976.
[18] Diptesh Ghosh, Ravi Kothari, Population Heuristics for the Corridor Allocation Problem, W.P. No. 2012-09-02, September 2012. Retrieved on September 14 2012 from Google search.
[19] Martin Grotschel, Olaf Holland (1991), Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51, pp. 141-202.
[20] Sunderesh S. Heragu, Andrew Kusiak (1988), Machine Layout Problem in Flexible Manufacturing Systems. Operations Research, Vol. 36, No. 2, Operations Research in Manufacturing (Mar. - Apr., 1988), pp. 258-268.
[21] S. S. Heragu, A. Kusiak (1991), Efficient Models for the Facility Layout Problem. European Journal of Operational Research, Vol. 53 (1991), pp. 1-13.
[22] S. S. Heragu, Facilities Design, Third Edition. Boca Raton, Florida: CRC Press, 2008.
[23] Philipp Hungerlaender, Miguel F. Anjos (January 2012), A Semidefinite Optimization Approach to Free-Space Multi-Row Facility Layout. Les Cahiers du GERAD. Retrieved from www.gerad.ca/fichiers/cahiers/G-2012-03.pdf
[24] Philipp Hungerlaender (April 2012), Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout. Retrieved from www.optimization-online.org./DB_HTML/2012/04/3432.html
[25] Michael Junger, Thomas M. Liebling, Dennis Naddef, George L. Nemhauser, William R. Pulleybank, Gerhart Reinelt, Giovanni Rinaldi, Lawrence A. Wolsey--Editors, 50 Years of Integer Programming 1958-2008. Berlin: Springer, 2010.
[26] R. L. Karg, G. L. Thompson (1964), A Heuristic Approach to Solving Travelling Salesman Problems. Management Science, Vol. 10, Number 2, pp. 225-248.
[27] K. Ravi Kumar, George C. Hadjinicola, Ting-li Lin (1995), A Heuristic Procedure for the Single-Row Facility Layout Problem. European Journal of Operational Research 87 (1995) 65-73.
[28] A. H. Land, A. G. Doig, An Automatic Method of Solving Discrete Programming Problems. Econometrica, Vol. 28, No. 3 (Jul., 1960), pp. 497-520.
[29] E. L. Lawler, M. D. Bell, A Method for Solving Discrete Optimization Problems. Operations Research, Vol. 14, No. 6 (Nov.-Dec., 1966), pp. 1098-1112.
[30] Robert F. Love, Jsun Y. Wong (1976), On Solving a One-Dimensional Space Allocation Problem with Integer Programming. INFOR, Vol. 14, No. 2, June 1976, pp. 139-143.
[31] Microsoft Corp., BASIC, Second Edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[32] Katta G. Murty, Operations Research: Deterministic Optimization Models. Prentice Hall, Upper Saddle River, New Jersey 07458, 1994.
[33] C. E. Nugent, T. E. Vollmann, J. Ruml (1968), An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research 16 (1968), pp. 150-173.
[34] Christopher J. Picone, Wilbert E. Wilhelm (1986), "A Perturbation Scheme To Improve Hillier's Solution to the Facilities Layout Problem": a Clarification. Management Science Vol. 32, No. 2, February 1986, pp. 253-254.
[35] Cliff T. Ragsdale, Spreadsheet Modeling and Decision Analysis, Fifth Edition. South-Westen, Cengage Learning, 2008.
[36] H. H. Rosenbrock (1960), An Automatic Method for Finding the Greatest or Least Value of a Function, Computer Journal Vol. 3, pp. 175-184.
[37] Donald M. Simmons (1969), One-Dimensional Space Allocation: An Ordering Algorithm. Operations Research, Vol. 17, No. 5 (Sep. - Oct., 1969), pp. 812-826.
[38] Tjark Vredeveld and Jan Karel Lenstra, On Local Search for the Generalized Graph Coloring Problem. Operations Research Letters, 31 (2003) 28-34.
[39] Wayne L. Winston, Munirpallam Venkataramanan, Introduction to Mathematical Programming: Operations Research, Volume One, Fourth Edition. Pacific Grove, CA 93950: Brooks/Cole--Thomson Learning, 2003.
[40] Wayne L. Winston, S. Christian Albright, Practical Management Science, Third Edition. Thomson/South-Western, 2007.
[41] Jsun Yui Wong (2009, July 18). An Integer Programming Computer Program Applied to One-Dimensional Space Allocation. Retrieved from http://wongsllllblog.blogspot.com/2009/07/
[42] Jsun Yui Wong (2009, November 2). A Computer Program for Relative Location of Circular Facilities. Retrieved on September 3, 2012, from http://wongsllllblog.blogspot.ca/2009/11/
[43] Jsun Yui Wong (2009, December 18). A Heuristic Nonlinear Integer Solver Applied to a Problem of Assignment of Facilities to Locations. Retrieved from http://wongsnewnewblog.blogspot.ca/2009/12/
[44] Jsun Yui Wong (2011, October 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a New Formulation of a Twelve-City Traveling Salesman Problem, Sixth Edition. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2011/10/27/
[45] Jsun Yui Wong (2012, September 27). A Nonlinear Integer/Discrete/Continuous Programming Solver Applied to a Linear Ordering Problem with 22 Facilities. Retrieved from http://computationalresultsfromcomputerprograms.wordpress.com/2012/9/27/
[46] Ji-Hui Zhang, Xin-He Xu (1999), An Efficient Evolutionary Programming Algorithm. Computers and Operations Research 26, 645-663.