Font Size: a A A

Study On Optimization Algorithms For A Multi-project Scheduling Problem With Resource Time-window Constraints

Posted on:2019-06-22Degree:MasterType:Thesis
Country:ChinaCandidate:S L LiFull Text:PDF
GTID:2359330542487655Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Resource Constraint Multi-Project Scheduling Problem(RCMPSP)widely exists in enterprise project management,since it is closely related to the project cost and production efficiency.Due to the complexity and diversity of enterprise project management,the models of RCMPSP have their own characteristics in different cases,and there is no general processing model at present.According to the actual requirements of the project management of an enterprise,based on the traditional RCMPSP,a Resource Constraint Multi-Project Scheduling Problem with Resource Time-Window Constraints(RCMPSPTWC)is proposed to solve the practical problem in this paper.In this model,some new concepts,such as jobs,sites,time windows,and some complex constraints,such as job constraints,site constraints,time window constraints,are introducted and taken into consideration.The objective is to minimize the makespan.First,based on the idea of traditional serial multi-project schedule generation scheme(SMPSGS),an improved version named ISMPSGS is designed and applied to solve the RCMPSPTWC problem,additionaly being incorporated seven priority rules.Experiments show that ISMPSGS is reasonable and effective,and superior to SMPSGS.The heuristic algorithm based on ISMPSGS can quickly generate a reasonable and feasible initial solution.Second,meta-heuristic algorithms used to optimize the aforementioned initial solution are proposed.By analyzing the characteristics of the discussed problem,we find that the sequence of job transfer is the key factor that restricts the scheduling result.A random sampling algorithm for generating job transfering sequence is designed to verify this observation and experimental results confirms it.On the base of this,the max-min ant system(MMAS)is adopted in the selection of the job transfer sequence,and an optimization algorithm based on ISMPSGS and MMAS is proposed.Experiments show that using MMAS to optimize the selection of job transfer sequence is reasonable and effective,and ISMPSGS is also superior to SMPSGS in meta-heuristic algorithm.Finally,in order to further handle the resource time window constraints,a two-stage algorithm based on ant colony and tabu search is proposed,in which the ant colony algorithm is used to determine the initial site of jobs and the tabu search algorithm is used to determine the subsequent sites.Experiments show that this algorithm is practical and efficient for solving RCMPSPTWC.When the number of iterations is fixed,this algorithm can find a better result than the algorithm based on ISMPSGS and MMAS at the expense of a little longer CPU time.The key algorithm based on this research has been used in practice.
Keywords/Search Tags:Resource-constrained multi-project scheduling problem, Time window constraints, Serial multi-project schedule generation scheme, Max-min ant system, Tabu search
PDF Full Text Request
Related items