4. Rescheduling with Controllable Processing Times and Job Rejection in the Presence of New Arrival Jobs and Deterioration Effect

This chapter considers a dynamic multi-objective machine scheduling problem in response to continuous arrival of new jobs with deterioration effect, under the assumption that jobs can be rejected and job processing time is controllable by allocating extra resources. By deterioration effect, we mean that each job’s processing time may be subject to change due to the capability deterioration with machine’s usage, i.e., the actual processing time of a job becomes longer if the job starts processing later. The operational cost and the disruption cost need to be optimized simultaneously. To solve these dynamic scheduling problems, a directed search strategy (DSS) is introduced into the elitist non-dominated sorting genetic algorithm (NSGA-II) to enhance its capability of tracking changing optimums while maintaining fast convergence. The DSS consists of a population re-initialization mechanism (PRM) to be adopted upon the arrival of new jobs and an offspring generation mechanism (OGM) during evolutionary optimization. PRM re-initializes the population by repairing the non-dominated solutions obtained before the disturbances occur, modifying randomly generated solutions according to the structural properties, as well as randomly generating solutions. OGM generates offspring individuals by fine-tuning a few randomly selected individuals in the parent population, employing intermediate crossover in combination with Gaussian mutations to generate offspring, and using intermediate crossover together with differential evolution based mutation operator. Both PRM and OGM aim to strike a good balance between exploration and exploitation in solving the dynamic multi-objective scheduling problem. Comparative studies are performed on a variety of problem instances of different sizes and with different changing dynamics. Experimental results demonstrate that the proposed DSS is effective in handling the dynamic scheduling problems under investigation.