Teaching-learning-based optimization algorithm for multi-skill resource constrained project scheduling problem

In this paper, a teaching-learning-based optimization algorithm (TLBO) is proposed to solve the multi-skill resource constrained project scheduling problem (MS-RCPSP) with makespan minimization criterion. A task-resource list-based encoding scheme is presented by combining the task list and the resource list, and a left-shift decoding scheme is developed to generate feasible schedules. To achieve satisfactory performances, the balance between global exploration and local exploitation is stressed in designing the TLBO algorithm. At the initialization stage, a balanced resource rule is proposed to generate the initial resource lists, and multiple task list rules are adopted in a hybrid way to initialize the task lists. At the teacher phase and the student phase, the two-point crossover and the resource-based local search are utilized to generate the promising task-resource lists. Moreover, a reinforcement phase is incorporated into the original TLBO with both the permutation-based and the resource-based local search strategies as an additional phase to enhance the local intensification capability. To investigate the influence of parameter setting on the TLBO, numerical tests based on Taguchi method of design of experiment are carried out. In addition, the effectiveness of the proposed balanced resource rule is shown by statistical comparisons with the random resource rule. Computational comparisons between TLBO and the existing algorithm also demonstrate the effectiveness and efficiency of the proposed TLBO in solving the MS-RCPSP.