Research On The Multi-skill Resource Constrained Project Scheduling Problem With Deteriorating Effect

Multi-skill resource constrained project scheduling problem(MS-RCPSP)is an important branch of resource constrained project problem(RCPSP),which is NP-hard.The executable scheduling plan of MS-RCPSP has to satisfy the restrictions of total resources,temporal constraints and the matching relations between resources and tasks simultaneously.The manager should assign resources to tasks according to the corresponding relationship and decide the starting time of each task under the premise of feasibility,aiming at minimizing the makespan,total tardiness,total cost and so on.In traditional project scheduling problem,the processing time of task is assumed to be a fixed constant.However,the processing time has uncertainty in most manufacturing and service systems,which leads to significant influence factors on final scheduling.Deteriorating effect,one of the most widespread influence factors,cannot be neglected.In scheduling with deterioration,the durations of tasks will vary in different starting times,sequences of tasks to be machined and assigned resources.In terms of theoretical research,most of the multi-skill resource constrained project scheduling problems with deterioration are NP-hard.With respect to the practical applications,they widely exist in software development,construction,aircraft manufacturing and so on.Consequently,it is of great theoretical value and realistic meaning to design effective and efficient optimization algorithms for these more complicated multi-skill resource constrained project scheduling problems with deterioration.This dissertation studies the multi-skill resource constrained project scheduling problems under two deterioration effects,including linear deterioration and step deterioration,and analyzes the complexities of researched problems.Due to the NP-hard nature of problem,the optimal solution is not available in acceptable polynomial time.Therefore,this dissertation designs some heuristic algorithms and intelligent optimization methods to efficient solutions on the basis of the analysis of problem and its solution architectural features.The main work and contributions are listed below.1.The single machine scheduling problem with linear deterioration under limited resources is researched for minimizing the makespanThis single machine scheduling problem is a special case of other processing environments.The analysis of its model can be helpful to deepen our understanding about the optimal solution architectural features and the fundamental characteristics.For researched problem,the 0-1 mixed integer programming model is formulated.The problem with the goal of minimizing maximum completion time is proved to be NP-hard.After the analysis of the problem characteristics,a heuristic algorithm named RCA based on the comparison of defined ratios and therefore a variable search algorithm RCA-LS are designed to solve the problem.Combined with the computation results from the exact solver LINGO for small-sized instances,simulation experiments carried on randomly generated instances demonstrate that the RCALS can match the optimal solutions derived from LINGO for all small-sized instances,and obtain schedules with shorter completion time at the cost of a little time than RCA.2.For multi-skill resource constrained project scheduling problem with step deterioration,two objective functions,including maxmimum completion time and total cost,are researchedAs a more general situation of single machine scheduling problem with deterioration under limited resources,the 0-1 mixed integer programming model is established.Both makespan and cost problem are proved to be NP-hard,and an improved tabu search algorithm integrated four neighborhood structures and one perturbation step is proposed.To generate its initial solution,successors list size-based priority rule is adapted as a simple heuristic.To verify the effectiveness of algorithm,computational experiments are performed on a set of benchmark instances compared with some state-of-the-art algorithms.Furthermore,the dataset is revised to incorporate the step deterioration.Numerical results show the proposed algorithm is a powerful solution methodology for solving the studied problem in terms of solutions quality.3.Multi-skill resource constrained project scheduling problem with step deterioration tasks and due date constraints is studied for minimizing total tardinessDuring the processing of scheduling tasks and resources,some extra demands are imposed on the due dates of tasks.To shed light on the researched problem,the 0-1 mixed integer programming model is formulated and the NP-hard nature of the total tardiness problem is demonstrated.Based on the architectural features of the optimal schedule,a heuristic algorithm named PL-MDD based on tasks priority level(PL)and modified due date(MDD)is programmed.Besides,a path relinking algorithm(PR)with a randomly local search phase also is designed to solve the considered problem.The computational experiments are conducted on a randomly generated dataset,which is derived from a existing benchmark dataset,to assess the algorithm performance.The final experimental results show that the proposed path relinking algorithm can solve the studied multi-skill resource constrained project scheduling problem with step-deterioration efficiently,satisfying the due date constraints as much as possible simultaneously.4.Multi-skill resource constrained project scheduling problem with linear deterioration is considered for minimizing the maximum completion timeFor the goal of minimizing the maximum completion time,the considered multi-skill resource constrained project scheduling problem with linear deterioration is discussed and its0-1 mixed integer programming model is constructed.To solve the absolutely NP-hard problem,a general variable neighborhood search-based memetic algorithm(GVNS-MA)is proposed,which integrates a solution recombination operator to explore new solution space and a local optimization procedure to reinforce the search of current space.During the process of algorithm design,a rapid evaluation mechanism(REM)is incorporated to evaluate the solution quality rapidly obtained in search process.Similarly,the proposed GVNS-MA is assessed on two sets of instances and achieves highly competitive results.Ones set of benchmark instances is commonly used in the literature where the capability of the proposed algorithm to find high quality solutions is demonstrated,compared with the state-of-the-art methodologies in the literature.The other set revises the former through incorporating the linear deterioration effect.Besides,the contrast experiments are carried out to investigate two key components of the proposed algorithm and their critical role to the success of the proposed method is confirmed.The experimental results not only demonstrate the superiority of GVNSMA,but also show the efficiency and stability for the reason of its insensitivity to the value range of penalty time.This dissertation considers the multi-skill resource constrained project scheduling problem on the premise of the tasks durations equipped with linear and step deteriorating effects.Taking three objective functions into account,i.e.the maximum completion time,the total tardiness and the total cost,four scheduling problems are investigated to get insight into the related characteristics of the optimal solutions and the corresponding solution algorithms are provided.This dissertation creatively put forward an idea to integrate the multi-skill resource constrained project scheduling problem with the deteriorating effects of tasks processing times.This research supplies some thoughts and methods to solve some specific types of problems,as well as enriches the study content of the scheduling field,which is helpful to shorter the makespan of actual project production,reduce the assumption of resources and improve the economic returns,with significantly important impact on engineering application.