برنامه های کاربردی بهینه سازی ازدحام ذرات در برنامه ریزی عملیات یکپارچه و زمان بندی

Integration of process planning and scheduling (IPPS) is an important research issue to achieve manufacturing planning optimisation. In both process planning and scheduling, vast search spaces and complex technical constraints are significant barriers to the effectiveness of the processes. In this paper, the IPPS problem has been developed as a combinatorial optimisation model, and a modern evolutionary algorithm, i.e., the particle swarm optimisation (PSO) algorithm, has been modified and applied to solve it effectively. Initial solutions are formed and encoded into particles of the PSO algorithm. The particles “fly” intelligently in the search space to achieve the best sequence according to the optimisation strategies of the PSO algorithm. Meanwhile, to explore the search space comprehensively and to avoid being trapped into local optima, several new operators have been developed to improve the particles’ movements to form a modified PSO algorithm. Case studies have been conducted to verify the performance and efficiency of the modified PSO algorithm. A comparison has been made between the result of the modified PSO algorithm and the previous results generated by the genetic algorithm (GA) and the simulated annealing (SA) algorithm, respectively, and the different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in both applications.

Process planning, an essential component for linking design and downstream manufacturing processes, is the act of preparing detailed operation instructions to transform an engineering design to a final part [1]. One of core activities in process planning is to decide which manufacturing resources to select and in which sequence to use, mainly based on the objective of achieving the correct quality, the minimal manufacturing cost and ensuring good manufacturability. Scheduling is used to determine the most appropriate moment to execute each operation for the launched production orders, taking into account the due date of these orders, a minimum makespan, a balanced resource utilisation, etc., to obtain high productivity in the workshop [2] and [3]. In job shop and batch manufacturing, both process planning and scheduling are responsible for the effective allocation and utilisation of resources. A process plan is usually determined before the actual scheduling with no regard for the scheduling objectives and with the assumption that all the resources are available. However, if a process plan is prepared offline without due consideration of the actual shop floor status, it may become unfeasible due to changes or constraints in the manufacturing environment and heavily unbalanced resource assignments. Also, due to the different objectives of these two systems, it is difficult to produce a satisfactory result in the simple sequential execution of the two systems. The merit of integrated process planning and scheduling (IPPS) is to increase production feasibility and optimality by combining both the process planning and scheduling problems [4]. The most recent works related to the IPPS optimisation can be generally classified into two categories: the enumerative approach and the simultaneous approach [2]. In the enumerative approach [3], [5], [6] and [7], multiple alternative process plans are first generated for each part. A schedule can be determined by iteratively selecting a suitable process plan from alternative plans of each part to replace the current plan until a satisfactory performance is achieved. The simultaneous approach [2], [8], [9], [10], [11] and [12] is based on the idea of finding a solution from the combined solution space of process planning and scheduling. In this approach, the process planning and scheduling are both in dynamic adjustment until specific performance criteria can be satisfied. Although this approach is more effective and efficient in integrating the two functions, it also enlarges the solution search space significantly. To address the above two optimisation problems, some optimisation approaches based on modern heuristics or evolutionary algorithms, such as the genetic algorithm (GA) (for operation sequencing problem [13], [14], [15], [16] and [17]; for IPPS problem [9], [10], [12] and [18]), simulated annealing (SA) algorithm (for operation sequencing problem [19] and [20]; for IPPS problem [2] and [5]), Tabu search algorithm (for operation sequencing problem [20] and [21], for IPPS problem [11]) and agent-based approach (for IPPS problem [22]) have been developed in the last two decades and significant improvements have been achieved. However, for parts with complex structures and features and multiple parts involved, these two optimisation processes are well known as complicated decision problems. The major difficulties include: (1) both operation sequencing and IPPS problems are NP-hard (non-deterministic polynomial) combinatorial optimisation problems. The search space is usually very large especially for IPPS problem because it involves multiple parts’ scheduling, and many previously developed methods could not find optimised solutions effectively and efficiently, and (2) there are usually a number of precedence constraints in sequencing operations and manufacturing resource utilisation constraints due to manufacturing practice and rules, which make the search more difficult. Therefore, it is necessary to develop efficient models for the operation sequencing and the IPPS optimisation problems and the optimisation algorithms need to be more agile and efficient to solve practical cases. Particle swarm optimisation (PSO) is a modern evolutionary computation technique based on a population mechanism [23]. It has been motivated by the simulation of the social behaviour of individuals (particles). This paper investigates the applications of this emerging optimisation algorithm into the intractable operation sequencing and the IPPS problems, and a newly developed PSO-based optimisation algorithm for them is elaborated. Firstly, the operation sequencing is defined and the representation of a solution for it by a particle is presented. Then, the representation model is expanded to represent the IPPS problem. The fitness functions of the solutions for these two problems are stated. Thirdly, the details of applying the PSO algorithm for them are described. Finally, case studies with computational experiments to test the algorithm are demonstrated, and a comparison between the result of the PSO algorithm and that of previous work is presented.

In this research, the operation sequencing and the IPPS problems have been modelled and a modified PSO algorithm has been used to optimise them. Solutions to the operation sequencing and the IPPS problems are encoded into PSO particles to intelligently search for the best sequence of the operations through leveraging the optimisation strategies of the PSO algorithm. To explore the search space more effectively, new operators, i.e., mutation, crossover and shift have been developed and incorporated to produce a modified PSO algorithm with improved performance. The GA and SA algorithms developed by Li et al. [21] and [33] and Li and McMahon [2] have been used to verify and compare the performance of the modified PSO algorithm with experiments of two groups’ parts. It is shown that the PSO algorithm can obtain a satisfactory optimisation result for these two problems. The characteristics of the GA, SA and PSO algorithms have been given, and for these cases the PSO algorithm has been shown to outperform both the GA and SA in the majority of applications by consideration of the computation efficiency, optimality and robustness. At this point in time the conclusions are limited by this computational experience, and more theoretical analysis needs to be made in future. However, there is still potential for further improvement in computation efficiency and optimality if introducing new operators and characteristics of other algorithms (For example, SA or Ant Colony Optimisation algorithm). And also with the population-based characteristics, a bounded rationality mechanism which is used in social science and economics can also be applied to the PSO algorithm to improve the performance further.