The improved genetic algorithm for job-shop scheduling problem with process sequence flexibility

This paper is focused on a new scheduling problem considering the sequence flexibility in classical job shop scheduling problem (SFJSP) that is very practical in most realistic situations. SFJSP consists of two sub-problems which are determining the sequence of flexible operations of each job and sequencing all the operations on the machines according to the determined operation sequence. An improved genetic algorithm (IGA) is proposed to solve this problem to minimize makespan. An improved chromosome encoding schema is proposed for IGA, in which sequence-based representation segment is added to the general operation-based representation segment. The corresponding crossover and mutation operators are designed to ensure the generation of feasible offspring chromosome for SFJSP. The effectiveness and efficiency of the proposed algorithm is tested by computational experiments on four practical instances of a bearing manufacturing corporation.