File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Artificial immune systems for job shop scheduling problems

TitleArtificial immune systems for job shop scheduling problems
Authors
Advisors
Advisor(s):Lau, HYK
Issue Date2012
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Qiu, X. [邱雪妮]. (2012). Artificial immune systems for job shop scheduling problems. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961757
AbstractEffective process scheduling is very important to the modern manufacturing production. This research addresses a classical scheduling problem — the job shop scheduling problem from the standpoint of both static and dynamic environment. In this study, the job shop scheduling problem (JSSP) is investigated in three aspects: (1) static JSSP that operates under a static scheduling environment with known information about the jobs and machines without unexpected events; (2) semi-dynamic JSSP which is developed based on static JSSP but violating the non-operation disruption assumption due to the presence of uncertainties occurring in the dynamic scheduling process; (3) dynamic online JSSP that operates under a dynamic operating environment in which jobs continuously arrive that are accompanied by unpredictable disruptions, such as machine failures. In the thesis, these three types of JSSP are solved by artificial immune systems (AIS) based algorithms. For static JSSP, a hybrid algorithm is proposed based on clonal selection theory and immune network theory of AIS, and particle swarm optimization (PSO). The clonal selection theory establishes the framework of the hybrid algorithm, while the immune network theory is applied to increase the diversity of antibody set which represents the solution candidates. The proposed framework involves the processes of selection, cloning, hypermutation, memory, and receptor editing. The PSO is designed to optimize the hypermutation process of the antibodies to accelerate the search procedure. This hybrid algorithm is tested with benchmark problems of different sizes and is compared with other methods. The results demonstrate the efficiency of the proposed algorithm, the effectiveness of PSO, and the contribution of long-lasting memory which is one of the key features of AIS. The semi-dynamic JSSP is handled by the rescheduling process. An extended deterministic dendritic cell algorithm (dDCA) is proposed to control the rescheduling process under considerations of the stability and efficiency of the scheduling system. The main role of the extended dDCA is to quantify the negative effect generated from the unexpected disturbances and to determine the best time to trigger the rescheduling process. This algorithm is tested on static benchmark problems with the existence of different kinds of disruptions. The experimental results demonstrate its capability of timely triggering the rescheduling process. The dynamic online JSSP is modeled as a multi-objective optimization problem. In this case, the immune network theory of AIS is hybridized with priority dispatching rules (PDRs) to establish the idiotypic network model for dispatching rules. This idiotypic network model drives the dispatching rule selection process under a dynamic scheduling environment. Based on the job shop situations represented by the antigens, the dispatching rules that perform best under specific conditions are selected as the antibodies of the idiotypic network model. Finally, the thesis proposes a generic framework of JSSP that combines the three different aspects studied in this research with corresponding scheduling strategies. The scheduling framework for a job shop system consists of four collaborating modules and is designed to solve various scheduling situations efficiently under a dynamic operating environment.
DegreeDoctor of Philosophy
SubjectProduction scheduling.
Artificial intelligence.
Immune system - Computer simulation.
Dept/ProgramIndustrial and Manufacturing Systems Engineering
Persistent Identifierhttp://hdl.handle.net/10722/180937

 

DC FieldValueLanguage
dc.contributor.advisorLau, HYK-
dc.contributor.authorQiu, Xueni.-
dc.contributor.author邱雪妮.-
dc.date.accessioned2013-02-07T06:20:55Z-
dc.date.available2013-02-07T06:20:55Z-
dc.date.issued2012-
dc.identifier.citationQiu, X. [邱雪妮]. (2012). Artificial immune systems for job shop scheduling problems. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4961757-
dc.identifier.urihttp://hdl.handle.net/10722/180937-
dc.description.abstractEffective process scheduling is very important to the modern manufacturing production. This research addresses a classical scheduling problem — the job shop scheduling problem from the standpoint of both static and dynamic environment. In this study, the job shop scheduling problem (JSSP) is investigated in three aspects: (1) static JSSP that operates under a static scheduling environment with known information about the jobs and machines without unexpected events; (2) semi-dynamic JSSP which is developed based on static JSSP but violating the non-operation disruption assumption due to the presence of uncertainties occurring in the dynamic scheduling process; (3) dynamic online JSSP that operates under a dynamic operating environment in which jobs continuously arrive that are accompanied by unpredictable disruptions, such as machine failures. In the thesis, these three types of JSSP are solved by artificial immune systems (AIS) based algorithms. For static JSSP, a hybrid algorithm is proposed based on clonal selection theory and immune network theory of AIS, and particle swarm optimization (PSO). The clonal selection theory establishes the framework of the hybrid algorithm, while the immune network theory is applied to increase the diversity of antibody set which represents the solution candidates. The proposed framework involves the processes of selection, cloning, hypermutation, memory, and receptor editing. The PSO is designed to optimize the hypermutation process of the antibodies to accelerate the search procedure. This hybrid algorithm is tested with benchmark problems of different sizes and is compared with other methods. The results demonstrate the efficiency of the proposed algorithm, the effectiveness of PSO, and the contribution of long-lasting memory which is one of the key features of AIS. The semi-dynamic JSSP is handled by the rescheduling process. An extended deterministic dendritic cell algorithm (dDCA) is proposed to control the rescheduling process under considerations of the stability and efficiency of the scheduling system. The main role of the extended dDCA is to quantify the negative effect generated from the unexpected disturbances and to determine the best time to trigger the rescheduling process. This algorithm is tested on static benchmark problems with the existence of different kinds of disruptions. The experimental results demonstrate its capability of timely triggering the rescheduling process. The dynamic online JSSP is modeled as a multi-objective optimization problem. In this case, the immune network theory of AIS is hybridized with priority dispatching rules (PDRs) to establish the idiotypic network model for dispatching rules. This idiotypic network model drives the dispatching rule selection process under a dynamic scheduling environment. Based on the job shop situations represented by the antigens, the dispatching rules that perform best under specific conditions are selected as the antibodies of the idiotypic network model. Finally, the thesis proposes a generic framework of JSSP that combines the three different aspects studied in this research with corresponding scheduling strategies. The scheduling framework for a job shop system consists of four collaborating modules and is designed to solve various scheduling situations efficiently under a dynamic operating environment.-
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/B49617576-
dc.subject.lcshProduction scheduling.-
dc.subject.lcshArtificial intelligence.-
dc.subject.lcshImmune system - Computer simulation.-
dc.titleArtificial immune systems for job shop scheduling problems-
dc.typePG_Thesis-
dc.identifier.hkulb4961757-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineIndustrial and Manufacturing Systems Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b4961757-
dc.date.hkucongregation2013-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats