Methods For Workflow Scheduling With Multiple Constraints

Project scheduling problem is very important and widespread in manufacturing, industri-al engineering and computer system. It is NP-hard because of multiple constraints, such as precedence relationships between activities, deadlines, resource availability. In this disserta-tion, four problems are considered which are the resource constrained single mode production scheduling problem, the preemptive project scheduling problem, the multi-mode resource con-strained project scheduling problem, and the setup-time and deadline constrained cloud work-flow scheduling problem. Characteristics of the problems are analyzed based on which math-ematical models are constructed. Methods are proposed for the problems under study, which provide effective decision-making supports for practical applications. Major contributions of this dissertation are summarized below.(1) For the non-preemptive single mode resource constrained project scheduling problem, a mathematical model is established to minimize makespan. The problem is decomposed into two sub-problems:activity list optimization and schedule generation. An improved particle swarm optimization is proposed for sequencing activities. Based on the obtained sequence, a fast scheduling schema is developed to schedule activities with the earliest start times. Experimental results show that the proposed method always outperforms the best existing algorithms.(2) For the preemptive single mode resource constrained project scheduling with minimiz-ing makespan, a mathematical model is established by analyzing the influence of preemption on production efficiency. Each activity is allowed to preempt only one time and it is divided into two sub-activities. The duration of each sub-activity is dynamic. A genetic algorithm is proposed for activity sequencing and sub-activity duration determination. A schedule generat-ing schema is designed in terms of the resource management list which determines durations of sub-activities. Experimental results show that preemption is effective for minimizing makespan of limited resource project scheduling.(3) For the multi-mode resource constrained project scheduling problem with makespan minimization, the mathematical model is constructed considering different demands of multi-mode activities on both resources and durations. This problem is divided into three sub-problems:mode assignment, activity sequencing and scheduling. A discrete particle swarm optimization is proposed. Two swarms are adopted to cooperatively optimize the mode assign-ment sub-problem and the activity sequence sub-problem respectively. A local search procedure is presented to improve quality of solutions. The forward/backward scheduling method is in-vestigated to obtain optimal schedules. Experimental results show that the cooperative method is effective for the problem under study.(4)For the workflow scheduling problem with setup time and deadline constraints in cloud manufacturing with cost minimization, a mathematical model is developed. A heuristic method is investigated for generating the initial population in terms of characteristics of the considered problem. The global best solution guides to find the optimal solution with a balance search process between diversification and intensification. A new probability model and an updating mechanism are introduced to sample the solution space. A hybrid estimation of distribution algorithm is proposed for selecting activity services. Experimental results show the proposed method is effective for the considered problem.