ORIGINAL_ARTICLE
Modeling and Scheduling University Course Timetabling Problems
This paper considers the problem of university course timetabling. In this problem, there are a set of courses, lecturers and classrooms. The objective is to assign schedule courses so as to maximize the total preference of lecturer-course, lecturer-day and course-day. The paper first formulates the problem in form of linear integer programming model. Using the model and commercial software, the small sized instances are optimally solved. Then, the paper proposes three different algorithms based on imperialist competitive algorithm, simulated annealing and variable neighborhood search. The algorithms employ several novel procedures such as encoding scheme, move operator, crossing operators. The algorithms are tuned and evaluated with optimal solutions found by the model. Then, they are evaluated by comparing their performance. The results show that imperialist competitive algorithm outperforms the other algorithms.
https://www.riejournal.com/article_49167_f374de6e7fbcaeb28d3b74731f25b75e.pdf
2016-11-01
1
15
10.22105/riej.2017.49167
University course scheduling
mathematical model
Metaheuristics
B.
Naderi
bahman.naderi@aut.ac.ir
1
Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran
LEAD_AUTHOR
[1] Aladag, C.H., Hocaoglu, G., and Basaran M.A. (2009). “The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem”, Expert Systems with Applications, 36, pp. 12349–12356.
1
[2] Al-Yakoob, S.M., and Sherali, H.D. (2007). “A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations”, European Journal of Operational Research, 180, pp. 1028–1044.
2
[3] Bardadym, V.A. (1996). “Computer-aided school and university timetabling: The new wave”. In E. Burke and P. Ross (Eds.), Practice and theory of automated timetabling. Lecture notes in computer science, 1153, pp. 22–45. Berlin: Springer.
3
[4] Boland, N., Hughes, B.D., Merlot, L.T.G., and Stuckey P.J. (2008). “New integer linear programming approaches for course timetabling”, Computers and Operations Research, 35, pp. 2209–2233.
4
[5] Burke, E.K., Eckersley, A.J., McCollum, B., Petrovic, S., and Qu R. (2010). “Hybrid variable neighbourhood approaches to university exam timetabling”, European Journal of Operational Research, 206, pp. 46–53.
5
[6] Burke, E.K., McCollum, B., Meisels, A., Petrovic, S., and Qu, R. (2007). “A graph-based hyper-heuristic for educational timetabling problems”, European Journal of Operational Research, 176, pp. 177–192.
6
[7] Causmaecker, P.D., Demeester P., and Vanden Berghe, G. (2009). “A decomposed metaheuristic approach for a real-world university timetabling problem”, European Journal of Operational Research, 195, pp. 307–318.
7
[8] Daskalaki, S., and Birbas, T. (2005). “Efficient solutions for a university timetabling problem through integer programming”, European Journal of Operational Research, 160, pp. 106–120.
8
[9] Dimopoulou, M., and Miliotis, P. (2004). “An automated university course timetabling system developed in a distributed environment: A case study”, European Journal of Operational Research, 153, pp. 136–147.
9
[10] Flesza, K., and Hindi, K.S. (2004). “Solving the resource-constrained project scheduling problem by a variable neighborhood search”, European Journal of Operational Research, 155, pp. 402–413.
10
[11] Hansen, P., and Mladenovic, N. (2001). “Variable neighborhood search: principles and applications”, European Journal of Operational Research, 130, pp. 449–467.
11
[12] Liao, C.J., and Cheng, C.C. (2007). “A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date”, Computers and Industrial Engineering, 52, pp. 404–413.
12
[13] Lü, Z., and Hao, J.K. (2010). “Adaptive Tabu Search for course timetabling”, European Journal of Operational Research, 200, pp. 235–244.
13
[14] Teoh, C.K., Wibowo, A., and Ngadiman, M.S. (2013). Review of state of the art for metaheuristic techniques in Academic Scheduling Problems, Artificial Intelligence Review, 10.1007/s10462-013-9399-6.
14
[15] Mladenovic, N., and Hansen, P. (1997). “Variable neighborhood search”, Computers and Operations Research, 24, pp. 1097–1100.
15
[16] MirHassani, S.A. (2006). “A computational approach to enhancing course timetabling with integer programming”, Applied Mathematics and Computation, 175, pp. 814–822.
16
[17] MirHassani, S.A., and Habibi, F., (2013). Solution approaches to the course timetabling problem, Artificial Intelligence Review, 39, pp. 133-149.
17
[18] Shiau, D.F. (2011). “A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences”, Expert Systems with Applications, 38, pp. 235–248.
18
[19] Turabieh, H., Abdullah, S. (2011). “An integrated hybrid approach to the examination time tabling problem”, Omega, 39, pp. 598–607.
19
[20] Wang, Y.Z. (2002). “An application of genetic algorithm methods for teacher assignment problems”, Expert Systems with Applications, 22, pp. 295–302.
20
[21] Wang, Y.Z. (2003). “Using genetic algorithm methods to solve course scheduling problems”, Expert Systems with Applications, 25, pp. 39-50.
21
[22] Zhang, D., Liu, Y., M’Hallah, R., and Leung, S.C.H. (2010). “A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems”, European Journal of Operational Research, 203, pp. 550–558.
22
[23] Atashpaz-Gargari, E., and Lucas, C., (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress Evolutionary Computers, Singapore, pp. 4661–4667.
23
[24] Atashpaz-Gargari, E., Hashemzadeh, F., Rajabioun, R., and Lucas, C., (2008). Colonial competitive algorithm, a novel approach for PID controller design in MIMO distillation column process. International Journal of Intelligent Computation and Cyberntic, 1, pp. 337–355.
24
[25] Bagher, M., Zandieh, M., and Farsijani, H., (2010). Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm. International Journal of Advanced Manufacturing Technology, 54, pp. 271–285.
25
[26] Banisadr, A.H., Zandieh, M., and Mahdavi, I., (2013). A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties. International Journal of Advanced Manufacturing Technology, pp. 981-989.
26
[27] Zhou, W., Yan, J., Li, Y., Xia, C., and Zheng, J., (2013). Imperialist competitive algorithm for assembly sequence planning. International Journal of Advanced Manufacturing Technology, 67, pp. 2207-2216.
27
[28] Kolon, M., (1999). Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, 113, pp. 123–136.
28
[29] Naderi, B., Zandieh, M., Khaleghi Ghoshe Balagh, A., and Roshanaei, V., (2009). “An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness”, Expert Systems with Applications, 36, pp. 9625–9633.
29
[30] Kahar, M.N.M., and Kendall, G. (2010). “The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution”, European Journal of Operational Research, 207, pp. 557–565.
30
ORIGINAL_ARTICLE
Solving a Bi-Objective Transportation Vehicle Routing Problem for Waste Collection by a New Hybrid Algorithm
This paper is an extension of the well-known vehicle routing problem (VRP) consisting of two stages. The first and second stages deal with the vehicle routing and transportation problems, respectively. Waste collection is one of the applications of the considered problem in a real world situation. A new mathematical model for this type of the problem is presented that minimizes the waste collection cost and decreases the risk posed to the environment for hazardous wastes transportation simultaneously. According to the NP-hard nature of the problem, a new multi-objective hybrid cultural and genetic algorithm (MOHCG) is proposed to obtain Pareto solutions. A straightforward representation for coding the given model is proposed to help us in reducing the computational time. To validate the proposed algorithm, a number of test problems are conducted and the obtained results are compared with the results of the well-known multi-objective evolutionary algorithm, namely non-dominated sorting genetic algorithm (NSGA-II), with respect to some comparison metrics. Finally, the conclusion is provided.
https://www.riejournal.com/article_49168_571c5c53d26517b33cf5760cca1b6098.pdf
2016-11-01
16
42
10.22105/riej.2017.49168
Waste collection
transportation vehicle routing
Multi-Objective Optimization
Cultural algorithm
H.
Farrokhi-Asl
1
School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
AUTHOR
R.
Tavakkoli-Moghaddam
tavakoli@ut.ac.ir
2
School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
LEAD_AUTHOR
[1] Golden B.L., Assad A.A., Wasil E.A., (2002). Routing vehicles in the real world: applications in solid waste, beverage food, dairy, and newspaper industries. In: Toth, P., Vigo, D.(Eds), The Vehicle Routing Problem. SIAM, Philadelphia, PA, 245-286.
1
[2] Sbihi A,. Eglese R.W., (2007). Combinatorial optimization and Green Logistics. 4OR.
2
[3] Lin C., Choy K.L., Ho G.T.S., Chung S.H., Lam H.Y., (2014), Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications. 31: 1118-1138.
3
[4] Dekker R., Fleischmann M., Inderfurth K., Van Wassenhov L.N., (2004). Reverse Logistics: quantitative models for closed loop supply chain. Berlin: Springer.
4
[5] Wy J., Kim B., Kim S., (2013). The rollon-rolloff waste collection routing problem with time windows, European Journal of Operational Research. 224: 466-476.
5
[6] Bonomo F., Duaran G., Larumbe F., Marenco J., (2012). A method for optimizing waste collection using mathematical programming: A Buenos Aires case study. Waste Management & Research. 30(3): 311-324.
6
[7] Sahoo S., Kim S., Kim B.I., Karas B., Popov Jr., (2005) Routing Optimization for waste management interface. 35(1):24-36.
7
[8] Kim B.I., Kim S., Sahoo S., (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research. 33: 3624-3642.
8
[9] Alumur S., Kara B.Y., (2007), A new model for the hazardous waste location routing problem. Computers & operations research; 34:1406-1423.
9
[10] Erkut E., Verter V., (1995).Hazardous materials logistics. In: Drezner Z, editor. Facility location. New York: Springer
10
[11] Gianikos I., (1998), A multi-objective programming model for location treatment sites and routing hazardous wastes. European Journal of Operational Research. 104: 333-342.
11
[12] Caballero R., Gonzalez M., Guerrero F.M., Molina J., Paralera C., (2007), Solving a multi-objective location routing problem with a metaheuristic based on tabu search. Application to real case in Andalusia. European Journal of Operational Research. 177: 1751- 1763.
12
[13] Martínez-Salazar, I. A., Molina, J., Ángel-Bello, F., Gómez, T., & Caballero, R. (2014). Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms. European Journal of Operational Research, 234(1), 25-36.
13
[14] Desrochers M., Laporte G., (1991). Improvements and extensions to the Miller– Tucker– Zemlin subtour elimination constraints, Operations Research Letters 10:27–36.
14
[15] Kara I., Laporte G., Bektas T., (2004). A note on the lifted Miller–Tucker–Zemlin sub tour elimination constraints for the capacitated vehicle routing problem, European Journal of Operational Research 15:8793–795.
15
[16] Deb K., Agrawal S., Pratab A., Meyunvian T., (2002). A fast elitist non-dominated sorting algorithm for multi-objective optimization NSGA-II. IEEE Transactions on Evolution Computation, 2182-2197.
16
[17] Reynolds, R.G., (1994), An introduction to cultural algorithms. In: A.V. Sebald and L.J. Fogel (Eds.), Proceedings of the Third Annual Conference on Evolutionary Programming, pp. 131–139. World Scientific, River Edge, New Jersey, USA.
17
[18] Best C., Che X., Reynolds R.G., Liu D., (2010), A multi-objective Cultural Algorithm, Evolutionary Computation (CEC) IEEE Congress on Barcelona, pp 1-9.
18
[19] Kennedy J, Eberhart R. Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks IV 1995; 1942–1948.
19
[20] Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. Second edition, MIT Press, 1992.
20
[21] Konak, A., Coit, Q. W., and Smith, A. (2006). Multi-objective optimization using genetic algorithms: A tutorial. Reliability Engineering & System Safety 91(9), 992-1007.
21
[22] Ho W., (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem,
22
Engineering Applications of Artificial Intelligence 21:548–557.
23
[23] Zitzler E., Thiele L., (1999). Multi-objective evolutionary algorithms: a comparative case study and strength Pareto approaches. IEEE Transactions on Evolutionary Computation, 257-271.
24
ORIGINAL_ARTICLE
The Methods of Ranking based Super Efficiency
The science of Data Envelopment Analysis (DEA) evaluates the effectiveness of decision making units. But, one of the problems of Data Envelopment Analysis (DEA) is that, if the number of units with the same efficiency equal to one was more than one, then we couldn’t select the best between them. It means that, we can’t rank them. Therefore, the need for ranking these units is considered by the managers. Different methods were proposed in this context. Most of these methods are modeled by DEA models. Due to the variety of ranking methods in DEA, this paper will describe ranking methods which are based on super-efficiency. More precisely, we introduced methods that rank using elimination (removing) of decision making units under the evaluation of observations(set). These methods have some advantages and disadvantages such as, model feasibility or infeasibility, stability or instability, being linear or nonlinear, being radial or non-radial, existence or non- existence of bounded optimal solution in objective function, existence or non- existence of multiple optimal solution, non-extreme efficient units ranking, complexity or simplicity of computational processes, that in this paper, Super Efficiency methods are compared with these eight properties.
https://www.riejournal.com/article_49169_156ab30bda5133dc88cce99bb1bffbda.pdf
2016-11-01
43
66
10.22105/riej.2017.49169
Data Envelopment Analysis
Ranking Technique
Efficiency
Super Efficiency
M.
Nayebi
1
Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran
AUTHOR
F
Hosseinzadeh Lotfi
farhad@hosseinzadeh.ir
2
Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran
LEAD_AUTHOR
[1] Jahanshahloo et al. (1387). Data Envelopment Analysis and its applications. Islamic Azad University. Science & Research Branch.
1
[2] Adler,N., Friedman,L., Sinuany-Stern,Z.,2002.Review of ranking method in the data envelopment analysis context. European Journal of operational research.140,249-265.
2
[3] Amirteimoori,A.,Jahanshahloo,G.R., Kordrostami,S.,2005. Ranking of decision making units in data envelopment analysis: A distance-based approach.Applied Mathematics and Computation 171.122-135.
3
[4] Andaerson,P., Petersen,N.C.1993(A Procedure for ranking efficient units in data envelopment Analysis, management science 39.1261-1264.)
4
[5] Banker, R.D., Charnes,A.,Cooper, W.W.,1984. Some method for estimating technical and scale inefficiencies in data envelopment analysis, management science,30(9).1078-1092.
5
[6] Charnes,A.,Cooper, W.W., Rhodes, E.,1978. Measuring efficiency of decision making units, Uroupean Journal of Operational Research.
6
[7] Jahanshahloo, G.R., Afzalinejad,M,2006b. A ranking method based on a full-inefficient frontier. Applied Mathemstical Modeling.30,248-260.
7
[8] Jahanshahloo, G.R., Hosseinzadeh Lotfi, F, Bagherzadeh Valami(2008). Ranking units using by cotext-dependent data envelopment analysis. applied mathematics Journal.
8
[9] Jahanshahloo, G.R., HosseinZadeh Lotfi,F,Junior,H.V., Akbarian,D,2006a. A new DEA rnking system based on changing the reference set. European Journal of operational research.
9
[10] Jahanshahloo, G.R., HosseinZadeh Lotfi,F, Rezai,H,Akbarian,D.,2004c. Ranking efficient DMUs using tchebycheff norm. working paper.
10
[11] Jahanshahloo, G.R., HosseinZadeh Lotfi,F, Shoja,N, Tohidi,G, Razavian,S,2004a. Ranking using 𝐿1 norm data envelopment analysis. Applied mathematic and computation.153(1),215-224.
11
[12] Jahanshahloo, G.R., HosseinZadeh Lotfi,F, Zhiani Rezaei,F, Rezaei Balf,F.2005. Using Monte carlo method for ranking efficient DMUs. Applied mathematic and computation.162.371-379.
12
[13] Jahanshahloo, G.R., Sanei,M, HosseinZadeh Lotfi,F ,Shoja,N,2004e. using the gradiant line for ranking DMUs in DEA. Applied mathematic and computation.151(1),209-217.
13
[14] Jahanshahloo, G.R., Sanei,M, Shoja,N,2004b. Modified ranking models, using the cocept of advantagein data envelopment analysis. Article in press.
14
[15] Jahanshahloo, G.R., Pourkarimi,L., Zarepishe,M.,2006c.Modified MAJ model for ranking of decision making unite in data envelopment analysis. Applied Mathmatics and computation.174.1054-1059.
15
[16] Khodabakhshi,M,2007.A super-efficiency model based on improved outputs in data envelopment analysis. Applied mathematic and computation,184,695-703.
16
[17] Li,Sh, Jahanshahloo, G.R., Khodabakhshi,M,2007. A super- efficiency model for ranking efficient units in data envelopment analysis. . Applied mathematics and computation.
17