Research On Flexible Resource Constrained Optimal Scheduling Problems

Flexible resource is popularly existing in the process of enterprise operation. Production development and manufacturing are playing important parts in this process, and the problems of production development project scheduling and shop scheduling are the kernel of them. Problems related with flexible resource constrained production development project scheduling and flow shop scheduling are studied in this dissertation. The flexible resource constrained scheduling problem is more complex than traditional ones, and is NP-hard in strong sense. The most important thing to solve the scheduling problem is mathematical modeling and algorithm construction, because effective scheduling algorithm can observably improve the utilization of resource and productivity. Study on flexible resource constrained scheduling problem is both important for theoretical and empirical perspectives. Study is carried out on the basis of most currently literature about project scheduling and shop scheduling. Systematic modeling methods, optimization theory, artificial intelligence theory and computational simulation based on Matlab6.5 are applied in this research, mathematical formulation and effective algorithm are proposed for the problems, valuable suggestions for enterprise manufacturing and development are raised eventually. Primary contents and results are as follows.(1) Concept of flexible resource is proposed based on the review of definition and classification, resource-ability matrix is develop to describe the flexibility distribution of resource, metrics for resource flexibility are discussed.(2) Basic theory and literature review about traditional project scheduling problem and flow shop problem are discussed. Problems about flexible resource constrained production development project scheduling, flow shop scheduling and flow shop scheduling with learning effect to be studied in this dissertation is proposed by analyzing basic assumptions of traditional scheduling problem.(3) Flexible resource constrained production project scheduling problem is studied. Mathematical formulation is presented for flexible resource constrained project scheduling problem (FRCPSP). Improved genetic algorithm is developed, in which priority-based encoding is used, method combining topological sort and maximum flow theory is carried out in decoding, and specific genetic operators are designed. The algorithm is coded in Matlab6.5 and computational results improve the effectiveness of the algorithm, demonstrate impact of different levels of resource flexibility and skill distribution of resource on project makespan, and suggest that reasonable scheduling strategy can improve performance of production development system.(4) Flexible resource constrained flow shop scheduling (FRCFSS) problem minimizing makespan is explored. Problem setting of FRCFSS is described and integrated programming model was constructed. Because the FRCFSS problem is NP-hard in the strong sense, the modified algorithm (MA) reasonably combines heuristic algorithm with genetic algorithm and tabu search algorithm and consists of3 modules, i. e. hybrid genetic algorithm based job sequencing module, critical operation based flexible resource allocation module and priority rules based operations start times decision module. Extensive simulation experiments demonstrate the effectiveness and robustness of the MA for FRCFSS problem. Comparison between traditional flow shop scheduling and FRCFSS implies that performance improvements associated with flexible resource scheduling are substantial.(5) Flexible resource constrained flow shop scheduling with learning effect (FRCFSSLE) problem is studied. Formulation and complexity of problem are analyzed. Heuristic algorithm for FRCFSSLE is constructed, which consists of 2 modules that respectively solve job sequencing, resource assignment and start time determination subproblems. Computational analysis improves properties for optimal resource assignment policy, improves effectiveness of the proposed algorithm, and demonstrates the performance improvements obtained by considering resource flexibility and learning effect in flow shop scheduling.