Modeling And Optimization Of Network Graph-based Integrated Process Planning And Scheduling Problems

Processing planning and scheduling are two important components in a manufacturing system. Process planning plays an important role from designing to manufacturing; it determines the precedence relationships between operations, machine tools and other parameters to generate feasible manufacturing schemes. Scheduling attempts to make certain criteria (e.g., makespan) optimized by assigning operations on machine tools with optimal sequence. At present, in most manufacturing systems the two functions are considered to be two separate systems. However, integrating process planning with scheduling will greatly improve the efficiency of a manufacturing system. Because of this, the integrated process planning and scheduling (IPPS) problem has received more and more research attentions.The traditional job shop scheduling problem is an NP-hard combinatorial optimization problem; the IPPS problem is certainly more complex than the (flexible) job shop scheduling problem. By far, traditional mathematical programming methods can only solve small scale IPPS instances. For large scale IPPS instances, heuristic and meta-heuristic algorithms are good choices since they can capture competitive solutions in reasonable time. Based on a deep study of the IPPS problem, corresponding mathematical models are estabilished and efficient solution methods for mono-objective, multi-objective, and dynamic IPPS problems are investigated..First, several network graph-specific mixed integer linear programming (MILP) models for the IPPS problem are proposed for the first time in this thesis based on a full study of existing models. The network graph-based modeling strategy is proposed in these models; and appropriate constraints are introduced to overcome the drawbacks of existing models. The established models are tested on small and large scale test-bed instances to verify their correctness. The experimental results denote that correct schedule schemes can be obtained using proposed models. However, affected by the nature of the NP-hard problem, the computational time of large scale instances is unsatisfactory.Secondly, aiming at the complexity of the problem, we introduce a meta-heuristic algorithm in this thesis for the mono-objective IPPS problem. A novel hybrid genetic algorithm is developed to solve the IPPS problem with makespan criterion by hiring a combination of the genetic algorithm (GA) and the variable neighborhood search (VNS) method to avoid being trapped into local optima. In the hybrid algorithm, a novel coding scheme with corresponding selection and crossover operators are proposed and two effective neighborhood structures are introduced to improve the efficiency of VNS. The proposed hybrid algorithm is tested on typical benchmark instances and the computational results are far better than those of other algorithms in existing literature. For Kim's benchmark,12 out of 24 instances have been improved to be the best solution by far, and 17 instances reach corresponding lower bounds.Thirdly, multi-objective IPPS problem is considered in this thesis since multiple objective requirements widely exist in real-world production situations. For three objectives considered in the real-life production situation, the overall finishing time (makespan), the maximum machine workload (MMW), and the total workload of machines (TWM), a multi-objective swarm intelligence algorithm is developed based on the mono-objective algorithm. Local search methods are introduced in the developed algorithm to seek for better non-dominated solutions. Different with other multi-objective algorithms that employ local search methods also, the distinct feature of the algorithm in this thesis is that the local search methods cover all the three objectives to obtain better Pareto front. Moreover, after the optimal Pareto front is captured, we adopt the TOPSIS method to determine the most satisfactory schedule scheme from the non-dominated solutions. The developed multi-objective algorithm is tested on typical benchmark instances and the experimental results are compared with those obtained by the well-known NSGA-II. Computational results verify the effectiveness of the proposed multi objective algorithm.Then, we investigate the dynamic IPPS problem in the thesis. Existing studies focus mainly on the static IPPS problem, which assumes that all the jobs to be processed are available at time zero. However, the dynamic disturbances, e.g., job random arrivals, are frequently occurring issues in a real-life situation. Thus, the resultant schedule scheme of the static IPPS problem is difficult to adapt itself to the real-life situation. The periodic and event-driven rescheduling methods are investigated in the thesis. Computational results show that the length of a scheduling interval, the number of new added jobs, and the shop utilization play an important role in improving the performance of a manufacturing system.Finally, a prototype system for integrated process planning and scheduling is developed based on the theoretical study; and the materials in this thesis together with further research directions are summarized in the last chapter.