Abstract: Identical parallel machines scheduling with sequence-dependent setup time is extensively applied in productive service and manufacturing industry and its main characteristic is computational complexity. Identical parallel machines scheduling with sequence-dependent setup time is to allot a set of jobs to be processed into identical parallel machines and sequence the jobs on each machine. It is a type of decision making with the purpose of optimizingsingle objective or multiple objectives. Identical parallel machines scheduling with sequence-dependent setup time to minimize the maximum job completion time is studied. The problem is formulated as a mathematical programming model. According to the structure characteristic of the problem, a genetic algorithm based on two-part chromosome representation is developed to obtain near optimal solutions. Based on the proposed mathematical programming model, a lower bound for the problem is introduced to evaluate the quality of near optimal solutions. Computational experiments are conducted on instances of different sizes, and the computational results show that the designed genetic algorithm can obtain reasonable solutions within an acceptable computational time.

Key words: Lower bound, Genetic algorithm, Identical parallel machines scheduling, Mathematical programming model, Sequence-dependent setup time