Abstract:

For a kind of larger scale Job Shop scheduling problem (JSSP) with the objective of the weighted tardy time, a self-adaptive hybrid genetic algorithm is proposed. First, for the reduction of the solving scale of the scheduling problem, on the basis of the defined scheduling characteristics—resource conflicting probability, all operations of the scheduling problem are divided dynamically into two kinds in the scheduling process: the first kind of operations with greater probability of the resource conflict, and the second kind of operations with less probability of the resource conflict. Furthermore, the chromosome is coded with three gene sequences: the gene sequence which consists of the above first kind of the operations, the gene sequence which consists of heuristic rules for determining the preference order of the second kind of operations, and a token gene sequence. Additionally, a fuzzy logic controller (FLC) is constructed to adjust adaptively the length of the first gene sequence so that the performance of the proposed genetic algorithm (GA) can be improved. The numerical computational results show that the proposed GA is effective for a kind of lager scale JSSP.

Key words: Job Shop scheduling problem, genetic algorithm, probability of the resource conflict, self-adaptive, fuzzy logic controller