決策者偏好學習與多目標排程最佳化

Preference Learning and Optimization for Multiple Objective Scheduling Problems

揚磊(Jan Leggen)

指導教授 ： 吳政鴻

國立臺灣大學/工學院/工業工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202103950

摘要

none

關鍵字

多標準決策 ； 未知的偏好函數 ； 支援向量機 ； 偏好學習

並列摘要

In manufacturing, multi-criteria decision making (MCDM) methods are already widely known and increasingly applied to multi-objective optimization problems. Oftentimes though, as in machine scheduling, conditions surrounding these problems remain constant, such as the number of available machines or the responsible decision maker (DM) assigning tasks to these machines. Therefore, for frequently changing job demands MCDM method users repeatedly solve very similar scheduling problems, while each instance of the MCDM method can require a large number of user interactions of the DM. Accordingly, vast historical user interaction and preference data is generated. One interactive MCDM method that enables DMs to find near optimal solutions for three-objective machine scheduling problems is the Interactive Centroid Method (ICM).
In this study, an attempt is made to create a preference learning method to complement the ICM. For a single user, the underlying unknown preference function remains constant and can be learned from historical user interaction data. The proposed SVM-based preference learning method can remain within a reasonable computational time, as well as retain the low number of user interactions that the ICM requires. Thereby, future demand scenarios can be solved preemptively and a solution is suggested to the decision maker. This approach has the potential to drastically reduce user decision time by replacing an average of 10 user interactions for each problem instance with one single final validation of the suggested solution.
The proposed SVC (Support Vector Classification) method is tested for linear and quadratic preference functions, as well as varying amounts of available historical preference data. Especially for quadratic preferences, the SVC results are in most cases an adequate replacement for further applications of the ICM.

並列關鍵字

Multi-criteria Decision-making ； Unknown Preference Functions ； Support Vector Machines ； Preference Learning

參考文獻

Arens, R. (2011) ‘Learning SVM Ranking Functions from User Feedback Using Document Metadata and Active Learning in the Biomedical Domain’, in Fürnkranz, J. and Hüllermeier, E. (eds) Preference Learning, Berlin, Heidelberg, Springer Berlin Heidelberg, pp. 363–383.

Bernroider, E. W. and Schmöllerl, P. (2013) ‘A technological, organisational, and environmental analysis of decision making methodologies and satisfaction in the context of IT induced business transformations’, European Journal of Operational Research, vol. 224, no. 1, pp. 141–153.

Boser, B. E., Guyon, I. M. and Vapnik, V. N. (1992) ‘A training algorithm for optimal margin classifiers’, Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. New York, NY, USA, ACM Press.

Brinker, K. (2003) ‘Incorporating Diversity in Active Learning with Support Vector Machines’, in Fawcett, T. and Mishra, N. (eds) Proceedings / Twentieth International Conference on Machine Learning: August 21 - 24, 2003, Washington, DC, USA, Menlo Park, Calif., AAAI Press.

Chou, Y.-L., Lin, T.-Y., Wu, J.-Z. and Wu, C.-H. (2020) ‘An interactive method for multicriteria dispatching problems with unknown preference functions’, Computers Industrial Engineering, vol. 144, p. 106462 [Online]. DOI: 10.1016/j.cie.2020.106462.