برنامه ریزی عملیات یکپارچه و زمان بندی توسط بهینه سازی کلونی مورچه ها بنگاه مدار
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|27039||2010||15 صفحه PDF||سفارش دهید||7287 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Industrial Engineering, Volume 59, Issue 1, August 2010, Pages 166–180
This paper presents an ant colony optimization (ACO) algorithm in an agent-based system to integrate process planning and shopfloor scheduling (IPPS). The search-based algorithm which aims to obtain optimal solutions by an autocatalytic process is incorporated into an established multi-agent system (MAS) platform, with advantages of flexible system architectures and responsive fault tolerance. Artificial ants are implemented as software agents. A graph-based solution method is proposed with the objective of minimizing makespan. Simulation studies have been established to evaluate the performance of the ant approach. The experimental results indicate that the ACO algorithm can effectively solve the IPPS problems and the agent-based implementation can provide a distributive computation of the algorithm
Process planning and scheduling are two important manufacturing planning activities which can greatly affect the performance of manufacturing systems. While process planning determines how a product is to be manufactured in accordance with its design specifications, scheduling is to assign manufacturing resources and schedule operations so that some relevant criteria, such as due dates, are satisfied. Traditionally, these two functions are performed sequentially. To establish the manufacturing requirements of a product, the process plan has to be prepared first, scheduling will then be performed to allocate manufacturing resources according to the process plan. Since the real-time status of the production facilities is not considered in either process planning or scheduling, in actual production, process plans and schedules may become deficient or infeasible due to dynamic changes in production. The merit of integrated process planning and scheduling (IPPS) is to increase the production feasibility and optimality by combining both the process planning and scheduling problems. Making use of alternative process plans as inputs of scheduling, it is then possible to select the routings and to sequence the operations for producing the parts according to the availability of the manufacturing resources and the current state of the manufacturing system. Since the actual process plan and the schedule are determined dynamically in accordance with the order details and the status of the shop, IPPS provides an essential solution on dynamic scheduling in a practical production environment. However, due to the combination of the two optimization problems and the flexibilities in the manufacturing systems, IPPS is a very complex problem. In most of the IPPS approaches, process selection and sequencing are still required to be predefined first, and the integrated approach is mainly to handle the choice of alternative routings in considering the scheduling constraints. This paper presents the application of the ant colony optimization (ACO) algorithm in an agent-based system to integrate process planning and shopfloor scheduling. Recently, collaborating advanced heuristics with multi-agent systems (MAS) has received significant attention in the agent community. While the distributive and autonomous features of the agent-based platform are maintained, the search-based heuristic is able to enhance the computational ability of the system. To evaluate the suitability and effectiveness of incorporating the heuristic search in MAS for solving the IPPS problem, a novel approach of integrating the ACO algorithm with the MAS-based IPPS system is proposed in this paper. The integration is important to demonstrate the extensibility of the agent-based system for the complex IPPS problems. With respect to the manufacturing order to produce N-parts with M-machines in a jobshop or similar kind of flexible manufacturing systems, a full set of processing flexibilities which includes alternative routings and alternative machines will be considered in the proposed IPPS model. The proposed ant algorithm takes advantage of distributed computation in the multi-agent platform. Each artificial ant is implemented as a software agent who runs separately and simultaneously, with a supervisory agent controlling the flow of the algorithm.
نتیجه گیری انگلیسی
An ant colony optimization algorithm is developed for the integrated process planning and scheduling problems. Motivated from the advantages of distributive computation and scalability of the MAS behaviours, the ACO algorithm is implemented on the established multi-agent platform. Artificial ants are implemented as software agents which run separately and simultaneously and they can be easily added or removed from the platform. To effect the ACO approach, a graph-based solution method is proposed to represent sets of alternative processes and machines. Artificial ants have to construct schedules by node selections in the graph. Inspired from the foraging behaviour of real ants, which are able to find shorter paths for food, the process plan and the schedule are determined dynamically with an objective of minimizing makespan. Furthermore, the two modifications, Elite Strategy and Convergence Avoidance, are able to enhance the performance of the algorithm. As evident from the experimental results, the implementation of the ACO algorithm in a multi-agent system is able to provide an extensible and practical solution method for the complex IPPS problems. Computation loading has been distributed effectively and the agent-based structure is more robust than a centralized implementation. As demonstrated in tests with different problem instances, the approach can effectively generate good solutions. In comparison with an evolutionary algorithm, the MAS-ACO algorithm has better performance on makespan minimization. Compared with the negotiation-based MAS, the ACO-based MAS is deficient in computational efficiency, in particular on those very complicated problems. However, the ACO-based implementation of MAS does not require the formulation of the non-trivial negotiation protocols and negotiation strategies as demanded in the negotiation-based MAS. In MAN and HAN, the negotiation approach demands that each negotiation partner (agent) has to be equipped with its own utility function during the negotiation process. It is difficult to develop the utility functions which can achieve optimal results all the time. The purpose of this paper is to evaluate the feasibility of applying the agent-based ACO approach to solve the IPPS problem. In terms of solution quality, although the proposed MAS–ACO approach is not really that competitive with the negotiation-based MAS approaches MAN and HAN, the success in applying the MAS–ACO approach indicates that it is worthwhile to pursue further work to extend and improve the existing MAS–ACO algorithm. For instance, effort could be devoted to parameter settings to improve the performances of the ACO algorithm. In this paper, parameters (such as C in Eq. (1) and α and ββ in Eq. (2)) are set by trial and error. To improve the performance of the algorithm, more effective tuning of the parameters is needed in order to improve the performance of the particular problem sets. An approach to tune the parameters is to identify the significance and sensitivity of each parameter based on the theory of Design of Experiments (DOE). For example, ANOVA (analysis of variance) has been conducted to understand the influences of the control parameters in Wang and Xie (2005). The current ACO involves an Elite Strategy. However, the current Elite Strategy is very simple, and it caters for schedule selection according to makespan only. Further modifications on the Elite Strategy can be done by filtering the schedules based on additional criteria (e.g. utilization, cost, etc.) and selectively applying the pheromone model to a group of the ants. Furthermore, for the pheromone updating model, this paper only applies a global updating rule to all the ants. To enhance the searching capability of the ants, the pheromone update rule can be modified by applying various local updating rules to specific groups of ants.