DNA Computing Algorithm for a school Timetable Problem

##plugins.themes.academic_pro.article.sidebar##

Published Mar 1, 2021
https://doi.org/10.47164/ijngc.v12i1.188
Download
pdf
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 12, Issue 1, March 2021

##plugins.themes.academic_pro.article.main##

Kuntala Boruah
Assistant Professor, School of Innovation and Technology, Assam Rajiv Gandhi University of Cooperative Management (ARGUCOM), Sivasagar, Assam, India
Manash Kapil Pathak
Assistant Controller of Examination, Mahapurusha Srimanta Sankaradeva Viswavidyalaya, Nagaon, Assam, India
Ranjan Sarmah
Assistant Professor, School of Innovation and Technology, Assam Rajiv Gandhi University of Cooperative Management (ARGUCOM), Sivasagar, Assam, India

Abstract

Deoxyribonucleic acid (DNA) computing is believed to have the potential to offer an effective approach to reduce any NP problem from exponential to polynomial time. Recently, use of biomolecules for solving scheduling problems has gained tremendous attention. In this paper a theoretical proof-of concept algorithm is proposed to address timetable scheduling problem which is a classical NP complete problem. The efficiency of this algorithm owes to the parallel processing property of DNA. Information relating to resources like the set of classes, teachers, time slots and subjects are encoded in the form of unique DNA sequences. Initially, all the possible (valid as well as invalid) allocations are generated and, in each step, the illegal sequences are discarded until finally left out with one or more potential solutions that satisfy the given set of constraints. The time complexity of the proposed algorithm is independent of the size of the problem. Moreover, the proposed algorithm can be applied to solve several other scheduling problems with necessary modifications.

##plugins.themes.academic_pro.article.details##

How to Cite
Kuntala Boruah, Manash Kapil Pathak, & Ranjan Sarmah. (2021). DNA Computing Algorithm for a school Timetable Problem. International Journal of Next-Generation Computing, 12(1), 62–74. https://doi.org/10.47164/ijngc.v12i1.188
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Adleman, L. M. 1994. Molecular computation of solutions to combinatorial problems.Science 266(5187), 1021-1024;1994. DOI: 10.1126/science.7973651.
  2. Lipton, R. J. 1995. DNA solution of hard computational problems. Science 268(5210),542-545. DOI: 10.1126/science.7725098.
  3. Roweis S., Winfree E., Burgoyne R., Chelyapov N.V.,Goodman M.F., Rothemund P.W.K. & Adleman L.M.1998. A sticker based model for DNA computation. J. Comput. Biol. 5,615–629. DOI: 10.1089/cmb.1998.5.615.
  4. Ouyang Q., Kaplan P.D., Liu S. & Libchaber. 1997. A DNA solution of the maximal clique problem. Science 278,446–449. DOI: 10.1126/ science. 278.5337. 446.
  5. Winfree E., Liu F., Wenzler L.A. & Seeman N.C. 1998.Design and self-assembly of two dimensional DNA crystals. Nature 394,539–544. DOI:10.1038/28998.
  6. Sakamoto K., Gouzu H., Komiya K., Kiga D., Yokoyama S., Yokomori T. & Hagiya M. 2000.Molecular computation by DNA hairpin formation. Science 288, 1223–1226. DOI: 10.1126/science.288.5469.1223.
  7. Smith L.M., Corn R.M., Condon A.E., Lagally M.G., Frutos A.G., Liu Q. & Thiel A.J.1998.A surface-based approach to DNA computation. J. Comput. Biol. 5, 255–267.DOI: 10.1089/cmb.1998.5.255.
  8. Li W.X., Xiao D.M. & He L. 2006. DNA ternary addition. Appl. Math. Comput. 182,977–986.DOI: 10.1016/j.amc.2006.04.051.
  9. Xiao D.M., Li W.X., Yu J., Zhang X.D., Zhang Z.Z. & He L.2006. Procedures for a dynamical system on {0,1}n with DNA molecules. BioSystems 84, 207–216.DOI: 10.1016/j.biosystems.2005.11.004.
  10. Wang Z.C., Huang D.M., Meng H.J. & Tang C.P. 2013. A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation; BioSystems 114,1–7.DOI: 10.1016/j.biosystems.2013.07.007.
  11. Chang W.L., Lin K.W., Chen J.C.,Wang C.C., Lu L.C., Guo M. & Ho M. 2012. Molecular Solutions of the RSA Public-key Cryptosystem on a DNA-based Computer. J. Supercomput. 61, 642–672.DOI: 10.1007/s11227-011-0627-z.
  12. Wang Z., Tan J., Huang D., Ren Y. & Ji Z. 2014. A biological algorithm to solve the assignment problem based on DNA molecules computation. Applied Mathematics and Computation 244, 183-190.DOI: 10.1016/j.amc.2014.06.098.
  13. Chang W.L., Ren T.T. & Feng M. 2014. Quantum Algorithms and Mathematical Formulations of Biomolecular Solutions of the Vertex Cover Problem in the Finite-Dimensional Hilbert Space. IEEE Trans. Nanobiosci. 14,121–128. DOI: 10.1109/TNB.2014.2375356.
  14. Wang Z. C., Zhang Y.M., Zhou W.H. & Liu H.F.2012. Solving traveling salesman problem in the Adleman-Lipton model. Appl. Math. Comput. 219, 2267–2270.
  15. DOI: 10.1016/j.amc.2012.08.073.
  16. C. C. Go’rElY.B.1963. The construction of class-teacher time-tables. Proc. IFIP Congr. 62, 73-77.
  17. Even, S., Itai, A., & Shamir, A.1975. On the complexity of time table and multi-commodity flow problems. In 16th Annual Symposium on Foundations of Computer Science , 184-193. IEEE. DOI: 10.1109/SFCS.1975.21.
  18. Chu, S. C., & Fang, H. L. 1999.Genetic algorithms vs. tabu search in timetable scheduling. In 1999 Third International Conference on Knowledge-Based Intelligent Information Engineering Systems Proceedings, 492-495. IEEE. DOI: 10.1109/ KES. 1999.820230.
  19. Cowling, P., Kendall, G., & Han, L. 2002.An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In Proceedings of the 2002 Congress on Evolutionary Computation 2, 1185-1190. IEEE. DOI: 10.1109/ CEC.2002.1004411.
  20. Sigl, B., Golub, M., & Mornar, V. 2003. Solving timetable scheduling problem using genetic algorithms. In Proceedings of the 25th International Conference on Information Technology Interfaces 2003, 519-524. IEEE. DOI:10.1109/ITI. 2003.1225396.
  21. Pezzella, Ferdinando, Gianluca Morganti, & Giampiero Ciaschetti.2008. A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research35(10) , 3202-3212.DOI: 10.1016/j.cor.2007.02.014.
  22. Bhaduri, A. 2009.University time table scheduling using genetic artificial immune network. In 2009 International Conference on Advances in Recent Technologies in Communication and Computing ,289-292. IEEE. DOI: 10.1109/ARTCom.2009.117.
  23. Ghaemi, S., Vakili, M. T., & Aghagolzadeh, A.2007. Using a genetic algorithm optimizer tool to solve University timetable scheduling problem.In 2007 9th International Symposium on Signal Processing and Its Applications , 1-4. IEEE. DOI: 10.1109/ISSPA.2007.4555397.
  24. Chu, S. C., Chen, Y. T., & Ho, J. H.2006. Timetable scheduling using particle swarm optimization. In First International Conference on Innovative Computing. Information and Control-Volume I, Vol. 3, 324-327. IEEE. DOI: 10. 1109/ ICICIC. 2006.541.
  25. Oprea, M. 2007. MAS_UP-UCT: A multi-agent system for university course timetable scheduling.International Journal of Computers Communications & Control 2(1),94-102.DOI: 10.15837/ijccc.2007.1.2341.
  26. Aycan, E., & Ayav, T. 2009. Solving the course scheduling problem using simulated annealing. In 2009 IEEE International Advance Computing Conference, 462-466. IEEE. DOI: 10.1109/IADCC.2009.4809055.
  27. Huisman, D.2006.A column generation approach for the rail crew re-scheduling problem.European Journal of Operational Research 180(1),163-173. DOI: 10.1016/j.ejor.2006.04.026.
  28. Chen, R. M., & Shih, H. F.2013.Solving university course timetabling problems using constriction particle swarm optimization with local search. Algorithms 6(2), 227-244. DOI: 10.3390/a6020227.
  29. Zhang, Y., D'Ariano, A., He, B. and Peng, Q. 2019. Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling. Transportation Research Part B: Methodological 127, 237-278.DOI: 10.1016/j.trb.2019.07.010.
  30. Zhong, J.H., Shen, M., Zhang, J., Chung, H.S.H., Shi, Y.H. and Li, Y., 2012. A differential evolution algorithm with dual populations for solving periodic railway timetable scheduling problem. IEEE Transactions on Evolutionary Computation 17(4,512-527. DOI: 10.1109/TEVC.2012.2206394.
  31. Ganguli, R., & Roy, S. 2017. A study on course timetable scheduling using graph coloring approach. International journal of computational and applied mathematics12(2), 469-485.
  32. Redl, T. A. 2007.University timetabling via graph coloring: An alternative approach.Congressus Numerantium187, 174.
  33. Burke, E. K., Elliman, D. G., & Weare, R. 1994.A university timetabling system based on graph colouring and constraint manipulation. Journal of research on computing in education 27(1),1-18; 1994.DOI:10.1080/08886504.1994.10782112.
  34. Wood, D. C. 1968.A system for computing university examination timetables. The Computer Journal 11(1), 41-47.DOI: 10.1093/comjnl/11.1.41.
  35. Cheng Z., Chen Z., Huang Y., Zhang X. & Xu J. 2010. Implementation of the timetable problem using self-assembly of DNA tiles. International Journal of Computers Communications & Control 5,490-505. DOI: 10. 15837/ ijccc. 2010. 4. 2507.
  36. Yin Z. & Chen M. 2010. Apply AcryditeTM Gel Separation to Solve Timetable Problem. Indonesian Journal of Electrical Engineering and Computer Science 10, 1111-1116.DOI: 10.15837/ijccc.2010.4.2507.
  37. Wang Z.C., Huang D.M., Tan J., Liu T.G., Zhao K. & Li L. 2015. A parallel algorithm for solving the n-queens problem based on inspired computational model. BioSystems131,22–29.DOI: 10.1016/j.biosystems.2015.03.004.
  38. Popov I. Y., Vorobyova A. V. & Blinova I. V. 2014. DNA-algorithm for timetable problem.International journal of bioinformatics research and applications 10, 145-156.DOI: 10.1504/IJBRA.2014.059520.