Abstract: Unrelated parallel machine scheduling problem with deteriorating jobs is studied with the objective of minimizing the maximum completion time. The processing time of a job varies with its beginning time which is denoted as an increasing function of its starting time. It is assumed that each job has its own different deterioration rate on each machine. A mathematical programming model is formulated for the NP-hard problem. An improved genetic algorithm based on two segment coding and self-adaptive adjustment of genetic parameters is then designed to make job scheduling and machine allocation more reasonable. Through the simulation experiments of different sized problems, the results show that the proposed algorithm has more advantages in both resolution time and solution quality.

Key words: maximum completion time, unrelated parallel machines scheduling, deteriorating jobs, two segment coding, self-adaptive strategy