Document Type : Research Paper

Author

Mechanical Engineering Department, School of Mechanical and Chemical Engineering, Institute of Technology, Woldia University, Woldia, Ethiopia

10.22105/riej.2021.266125.1179

Abstract

This paper presented greedy algorithm for solving student allocation problem that has arisen in internship program. In internship program, engineering students stay one semester in industries which are located across the country and teachers visit students once/twice for supervision during the program. As the industries scatter across the country, teachers spend long time on travel. And this results in wastage of teachers working time and money spent for transport. Therefore, allocating students to universities near the internship location extensively reduces the transport time and money spent for transport. For the current study, we consider 4th mechanical engineering students who are currently working in the industry. The proposed approach extensively decrease the distance traveled from 23,210 km to 2,488.8 km and the time spent on the road from 397 hrs. 40 min to 51 hrs. 30 min. and finally, the results obtained from the greedy algorithm is compared with other heuristics (i.e., Genetic algorithm and Particle swarm optimization) and the greedy algorithm outperforms the other methods.

Keywords

Main Subjects

  • Basirzadeh, H. (2012). Ones assignment method for solving assignment problems. Applied mathematical sciences6(47), 2345-2355.
  • Naderi, B. (2016). Modeling and scheduling university course timetabling problems. International journal of research in industrial engineering5(1 (4)), 1-15.
  • Syakinah, F., Abdul-Rahman, S., & Abd Rahman, R. (2018). An assignment problem and its application in education domain: a review and potential path. Research article. Advances in operations research. https://doi.org/10.1155/2018/8958393
  • Anwar, A. A., & Bahaj, A. S. (2003). Student project allocation using integer programming. IEEE transactions on education46(3), 359-367. DOI: 1109/TE.2003.811038
  • Pan, L., Chu, S. C., Han, G., & Huang, J. Z. (2009, September). Multi-criteria student project allocation: a case study of goal programming formulation with dss implementation. The eighth international symposium on operations research and its applications (ISORA’09), Zhangjiajie, China(pp. 75-82). https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.4029&rep=rep1&type=pdf
  • Calvo-Serrano, R., Guillén-Gosálbez, G., Kohn, S., & Masters, A. (2017). Mathematical programming approach for optimally allocating students' projects to academics in large cohorts. Education for chemical engineers20, 11-21. https://doi.org/10.1016/j.ece.2017.06.002
  • Harper, P. R., de Senna, V., Vieira, I. T., & Shahani, A. K. (2005). A genetic algorithm for the project assignment problem. Computers & operations research32(5), 1255-1265. https://doi.org/10.1016/j.cor.2003.11.003
  • Ramli, R., & Bakar, E. M. N. E. A. (2003). The assignment of projects to students using 0-1 integer programming. Operational research and its applications: research trends (APORS 2003)2.
  • Zukhri, Z., & Omar, K. (2008). Solving new student allocation problem with genetic algorithm: a hard problem for partition based approach.  J. soft comput. appl2, 6-15.
  • Kenekayoro, P., Mebine, P., & Zipamone, B. G. (2020). Population based techniques for solving the student project allocation problem. International journal of applied metaheuristic computing (IJAMC)11(2), 192-207. DOI: 4018/IJAMC.2020040110
  • Manlove, D., Milne, D., & Olaosebikan, S. (2020). Student-project allocation with preferences over projects: Algorithmic and experimental results. Discrete applied mathematics. https://doi.org/10.1016/j.dam.2020.08.015
  • Li, X. (2017). Solving transportation problems with warehouse locations based on greedy algorithm. International conference on advances in materials, machinery, electrical engineering (ammee), advances in engineering research, 114, 693-697.
  • Haket, C., van der Rhee, B., & de Swart, J. (2020). Saving time and money and reducing carbon dioxide emissions by efficiently allocating customers. INFORMS journal on applied analytics50(3), 153-165. https://doi.org/10.1287/inte.2020.1028
  • Qu, G., Brown, D., & Li, N. (2019). Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica105, 206-215. https://doi.org/10.1016/j.automatica.2019.03.007
  • Ribas, I., Companys, R., & Tort-Martorell, X. (2019). An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert systems with applications121, 347-361. https://doi.org/10.1016/j.eswa.2018.12.039
  • Ying, K. C., Lin, S. W., Cheng, C. Y., & He, C. D. (2017). Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems. Computers & industrial engineering110, 413-423. https://doi.org/10.1016/j.cie.2017.06.025
  • Myszkowski, P. B., Olech, Ł. P., Laszczyk, M., & Skowroński, M. E. (2018). Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained project scheduling problem. Applied soft computing62, 1-14. https://doi.org/10.1016/j.asoc.2017.10.014
  • Buijs, P., Alvarez, J. A. L., Veenstra, M., & Roodbergen, K. J. (2016). Improved collaborative transport planning at Dutch logistics service provider Fritom. Interfaces46(2), 119-132. https://doi.org/10.1287/inte.2015.0838
  • Brandeau, M. L., & Chiu, S. S. (1989). An overview of representative problems in location research. Management science35(6), 645-674. https://doi.org/10.1287/mnsc.35.6.645
  • Daskin, M. S. (2011). Network and discrete location: models, algorithms, and applications. John Wiley & Sons.
  • ReVelle, C. S., & Eiselt, H. A. (2005). Location analysis: a synthesis and survey. European journal of operational research165(1), 1-19. https://doi.org/10.1016/j.ejor.2003.11.032