Algorithm Design And Information Value For Multi-mode Resource Constrained Project Scheduling Problem

With the fourth industrial revolution dominated by intelligent manufacturing,production has shifted from the single factory production to multi-factory production network.To become competitive in today’s rapidly changing market requirements,many factories have shifted from a centralized to a more decentralized structure in many areas of decision making including scheduling.With the intelligent transformation of manufacturing industry,the original scheduling mode can not meet the demand of manufacturing industry.Besides,the recent remarkable attention in distributed production management in both academia and the industry has demonstrated the significance of distributed scheduling.This paper mainly studies the algorithm design and information value of two variant problems of classical multi-resource constrained project scheduling problem.For a practical problem of the first variant,this paper focuses on a common production-transportation problem in the manufacturing supply chain.There are three types of decision makers: manufacturers,customers and resource manager.The information in the system is divided into production capacity information,resource constraint information and other basic information.With different levels of information sharing,different solution approaches are proposed.With complete information sharing,this paper first formulates a mixed integer programming model with the consideration of multiple products and resource-sharing among all manufacturers.Then this paper proposes some enhancement constraints and a Lagrangian relaxation decomposition algorithm is designed to solve the problem.Without production capacity information sharing,a distributed model is formulated,that is,the production planning model for the manufacturers and the vehicle scheduling problem for the third party resource manager.Then a column generation based distributed algorithm is designed to solve the model.Without consideration of production capacity information and resource constraint information,this paper designs a new coding method and decoding program and proposes a multi-agent system based distributed algorithm to solve the problem.From the perspective of information value,five algorithms are adopted to solve the problem according to the different degree of information sharing.Then,according to the definition of information value proposed in this paper,the information value is analyzed.Finally,the integrated model and distribution model are compared by numerical experiments,and the information value of production capacity information,resource constraint information,basic information and complete information is obtained by comparing the solutions of each algorithm.For the second variant,i.e.,multi-resource constrained project scheduling problem with uncertain activity duration time,this paper first formulates a deterministic model.Based the concept of forbidden set,the model is reformulated,and a chance-constrained model by adding a probabilistic constraint is proposed.Then the problem is solved by a sample average approximation method and branch-and-cut algorithm.Finally,extensive computational experiments are conducted to prove the effectiveness of the proposed model and algorithm compared with previous algorithms.