An Evolutionary Hyper-heuristic for the Software Project Scheduling Problem

详细信息    查看全文

• 关键词：Software project scheduling ; Hyper ; heuristics ; Adaptive operator selection ; Sliding multi ; armed bandit
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9921
• 期：1
• 页码：37-47
• 全文大小：657 KB
• 参考文献：1.Alba, E., Francisco, C.: Software project management with GAs. Inf. Sci. 177, 2380–2401 (2007)CrossRef
  2.Burke, E., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., Woodward, J.: A classification of hyper-heuristic approaches. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management, vol. 146, pp. 449–468. Springer, Berlin (2010)CrossRef
  3.Blazewicz, J., Lenstra, J., Rinnooy, K.: Scheduling subject to resource constraints: classification and complexity. Discret Appl. Math. 5, 11–24 (1983)MathSciNet CrossRef MATH
  4.Crawford, B., Soto, R., Johnson, F., Monfroy, E., Paredes, F.: A max-min ant system algorithm to solve the software project scheduling problem. Expert Syst. Appl. 41, 6634–6645 (2014)CrossRef
  5.Chang, C., Jiang, H., Di, Y., Zhu, D., Ge, Y.: Time-line based model for software project scheduling with genetic algorithms. Inf. Softw. Tech. 50, 1142–1154 (2008)CrossRef
  6.Chen, W., Zhang, J.: Ant colony optimization for software project scheduling and staffing with an event-based scheduler. IEEE Trans. Softw. Eng. 39(1), 1–17 (2013)CrossRef
  7.Consoli, P.A., Minku, L.L., Yao, X.: Dynamic selection of evolutionary algorithm operators based on online learning and fitness landscape metrics. In: Dick, G., et al. (eds.) SEAL 2014. LNCS, vol. 8886, pp. 359–370. Springer, Heidelberg (2014)
  8.Ding, R., Jing, X.: Five principles of project management in software companies. In: Project Management Technology, vol. 1 (2003). (in Chinese)
  9.Jorge, A., Alcaraz, S., Ochoa, G., Swan, J., Carpio, M., Puga, H., Burke, E.: Effective learning hyper-heuristics for the course timetabling problem. Eur. J. Oper. Res. 238, 77–86 (2014)MathSciNet CrossRef MATH
  10.Li, K., Fialho, A., Kwong, S., Zhang, Q.: Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 18(1), 114–130 (2014)CrossRef
  11.Minku, L., Sudholt, D., Yao, X.: Improved evolutionary algorithm design for the project scheduling problem based on runtime analysis. IEEE Trans. Softw. Eng. 40(1), 83–102 (2014)CrossRef
  12.Montoya, C., Bellenguez-Morineau, O., Pinson, E., Rivreau, D.: Branch-and-price approach for the multi-skill project scheduling problem. Optim. Lett. 8, 1721–1734 (2014)MathSciNet CrossRef MATH
  13.Shen, X., Minku, L., Bahsoon, R., Yao, X.: Dynamic software project scheduling through a proactive-rescheduling method. IEEE Trans. Softw. Eng. 24 December 2015. doi:10.​1109/​TSE.​2015.​2512266
  14.Penta, M., Harman, M., Antoniol, G.: The use of search-based optimization techniques to schedule and staff software projects: an approach and an empirical study. Softw. Pract. Exper. 41, 495–519 (2011)CrossRef
  15.Xiao, J., Ao, X., Tang, Y.: Solving software project scheduling problems with ant colony optimization. Comput. Oper. Res. 40, 33–46 (2013)MathSciNet CrossRef
  16.Xiao, J., Osterweil, L.J., Wang, Q., Li, M.: Dynamic resource scheduling in disruption-prone software development environments. In: Rosenblum, D.S., Taentzer, G. (eds.) FASE 2010. LNCS, vol. 6013, pp. 107–122. Springer, Heidelberg (2010)CrossRef
  17.Yannibelli, V., Amandi, A.: A knowledge-based evolutionary assistant to software development project scheduling. Expert Sys. Appl. 38, 8403–8413 (2011)CrossRef
  
• 作者单位：Xiuli Wu (19)
  Pietro Consoli (20)
  Leandro Minku (21)
  Gabriela Ochoa (22)
  Xin Yao (20)
  
  19. Department of Logistics Engineering, School of Mechanical Engineering, University of Science and Technology Beijing, Beijing, China
  20. CERCIA, School of Computer Science, University of Birmingham, Birmingham, UK
  21. Department of Computer Science, University of Leicester, Leicester, UK
  22. Computing Science and Mathematics, University of Stirling, Stirling, UK
  
• 丛书名：Parallel Problem Solving from Nature ¨C PPSN XIV
• ISBN：978-3-319-45823-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9921

文摘

Software project scheduling plays an important role in reducing the cost and duration of software projects. It is an NP-hard combinatorial optimization problem that has been addressed based on single and multi-objective algorithms. However, such algorithms have always used fixed genetic operators, and it is unclear which operators would be more appropriate across the search process. In this paper, we propose an evolutionary hyper-heuristic to solve the software project scheduling problem. Our novelties include the following: (1) this is the first work to adopt an evolutionary hyper-heuristic for the software project scheduling problem; (2) this is the first work for adaptive selection of both crossover and mutation operators; (3) we design different credit assignment methods for mutation and crossover; and (4) we use a sliding multi-armed bandit strategy to adaptively choose both crossover and mutation operators. The experimental results show that the proposed algorithm can solve the software project scheduling problem effectively.