Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một phương pháp heuristic đa giai đoạn dựa trên lập trình nguyên cho việc lập thời khóa biểu lớp học và phân công giảng viên
Tóm tắt
Chúng tôi xem xét một vấn đề lập thời khóa biểu và phân công giảng viên liên quan đến việc huấn luyện định kỳ số lượng lớn nhân viên tại một nhà phân phối điện tại Úc. Vấn đề này khác với các vấn đề lập thời khóa biểu truyền thống tại các trường trung học và đại học đã được nghiên cứu trong tài liệu ở một số khía cạnh. Chúng tôi đề xuất một phương pháp heuristic ba giai đoạn bao gồm tạo thời khóa biểu, cải thiện thời khóa biểu và phân công giảng viên. Các mô hình lập trình nguyên tuyến tính quy mô lớn cho cả hai thành phần lập thời khóa biểu và phân công giảng viên cũng được đề xuất, và một số ràng buộc hoạt động độc đáo được thảo luận. Chúng tôi cho thấy rằng phương pháp giải quyết này có khả năng tạo ra những giải pháp tốt trong khoảng thời gian thực tế chấp nhận được.
Từ khóa
#lập thời khóa biểu #phân công giảng viên #phương pháp heuristic #lập trình nguyên tuyến tính #ràng buộc hoạt độngTài liệu tham khảo
Akkoyunlu, E. A. (1973). A linear algorithm for computing the optimum university timetable. The Computer Journal, 16(4), 347–350.
Balakrishnan, N., & Wong, R. T. (1990). A network model for the rotating workforce scheduling problem. Networks, 20(1), 25–42.
Birbas, T., Daskalaki, S., & Housos, E. (1997). Course and teacher scheduling in hellenic high schools. In 4th Balkan conference on operational research, Thessaloniki, Greece.
Bölte, A., & Thonemann, U. W. (1996). Optimizing simulated annealing schedules with genetic programming. European Journal of Operational Research, 92(2), 402–416.
Burke, E., Elliman, D., & 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.
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.
Carter, M. W., & Tovey, C. A. (1992). When is the classroom assignment problem hard? Operations Research, 40(1-supplement-1), S28–S39.
Carter, M. W., Laporte, G., & Lee, S. Y. (1996). Examination timetabling: Algorithmic strategies and applications. Journal of the Operational Research Society, 373–383.
Dantzig, G. B. (1954). Letter to the editor-a comment on edie’s traffic delays at toll booths. Journal of the Operations Research Society of America, 2(3), 339–341.
de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2), 151–162.
Dimopoulou, M., & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130(1), 202–213.
Dorneles, Á. P., de Araújo, O. C., & Buriol, L. S. (2014). A fix-and-optimize heuristic for the high school timetabling problem. Computers & Operations Research, 52, 29–38.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.
Fischetti, M., & Widmayer, P. (2008). Towards solving very large scale train timetabling problems by lagrangian relaxation. In 8th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS08) (Vol. 9).
Gunawan, A., Ng, K., & Poh, K. (2008). A hybrid algorithm for the university course timetabling problem. In Proceedings of the 7th international conference on the practice and theory of automated timetabling.
IBM. (2014). IBM CPLEX optimizer. http://www.ibm.com/software/commerce/optimization/cplex-optimizer/.
IBM. (2015). IBM user’s manual for CPLEX. ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex.pdf.
Kahar, M. M., & 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(2), 557–565.
Karp, R. M. (1972). Reducibility among combinatorial problems. Berlin: Springer.
Lawrie, N. L. (1969). An integer linear programming model of a school timetabling problem. The Computer Journal, 12(4), 307–316.
Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167–190.
Marx, D. (2004). Graph colouring problems and their applications in scheduling. Electrical Engineering, 48(1–2), 11–16.
Mehta, N. K. (1981). The application of a graph coloring method to an examination scheduling problem. Interfaces, 11(5), 57–65.
Minerals Council of Australia. (2013). Training and education activity in the minerals sector. http://www.minerals.org.au/file_upload/files/reports/Final_Report_Minerals_Council_2013.pdf.
Neufeld, G., & Tartar, J. (1974). Graph coloring conditions for the existence of solutions to the timetable problem. Communications of the ACM, 17(8), 450–453.
Papoutsis, K., Valouxis, C., & Housos, E. (2003). A column generation approach for the timetabling problem of greek high schools. Journal of the Operational Research Society, 54(3), 230–238.
Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261–293.
Qualizza, A., & Serafini, P. (2005). A column generation scheme for faculty timetabling. In Practice and theory of automated timetabling V (pp. 161–173). Berlin: Springer.
Schimmelpfeng, K., & Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. OR Spectrum, 29(4), 783–803.
Ülker, Ö., Özcan, E., & Korkmaz, E. E. (2007) Linear linkage encoding in grouping problems: Applications on graph coloring and timetabling. In Practice and theory of automated timetabling VI (pp. 347–363). Berlin: Springer.
Yao, X. (1995). A new simulated annealing algorithm. International Journal of Computer Mathematics, 56(3–4), 161–168.