Artificial immune systems for job shop scheduling problems

Abstract

Effective 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.