File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: An enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system

TitleAn enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system
Authors
Advisors
Advisor(s):Wong, TN
Issue Date2012
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Zhang, S. S. [张思成]. (2012). An enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961806
AbstractProcess planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed.
DegreeMaster of Philosophy
SubjectProduction planning - Mathematical models.
Production scheduling - Mathematical models.
Multiagent systems.
Ant algorithms.
Dept/ProgramIndustrial and Manufacturing Systems Engineering
Persistent Identifierhttp://hdl.handle.net/10722/180985

 

DC FieldValueLanguage
dc.contributor.advisorWong, TN-
dc.contributor.authorZhang, Sicheng.-
dc.contributor.author张思成.-
dc.date.accessioned2013-02-07T06:22:02Z-
dc.date.available2013-02-07T06:22:02Z-
dc.date.issued2012-
dc.identifier.citationZhang, S. S. [张思成]. (2012). An enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961806-
dc.identifier.urihttp://hdl.handle.net/10722/180985-
dc.description.abstractProcess planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.source.urihttp://hub.hku.hk/bib/B49618064-
dc.subject.lcshProduction planning - Mathematical models.-
dc.subject.lcshProduction scheduling - Mathematical models.-
dc.subject.lcshMultiagent systems.-
dc.subject.lcshAnt algorithms.-
dc.titleAn enhanced ant colony optimization approach for integrating process planning and scheduling based on multi-agent system-
dc.typePG_Thesis-
dc.identifier.hkulb4961806-
dc.description.thesisnameMaster of Philosophy-
dc.description.thesislevelMaster-
dc.description.thesisdisciplineIndustrial and Manufacturing Systems Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b4961806-
dc.date.hkucongregation2013-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats