A hybrid genetic algorithm with two-stage dispatching heuristic for a machine scheduling problem with step-deteriorating jobs and rate-modifying activities

• We study machine scheduling with step-deteriorating jobs and rate-modifying activities.
• We derive a mixed integer programming model for the problem.
• We propose hybrid GA with two-stage dispatching heuristic.
• We simultaneously determine the schedule of jobs and the number and positions of RMAs.

This article is concerned with a single machine scheduling problems that integrate by step-deterioration along with multiple rate-modifying activities (RMAs). The actual processing time of a job is defined by a step function of its starting time and a specific deterioration threshold. The starting rate of the actual processing time of jobs is restored through the application of RMAs, which recover the original processing time. In this scheduling environment, we simultaneously determine the schedule of step-deteriorating jobs and the number and positions of RMAs to minimize the makespan. We derive a mixed integer programming model to obtain the optimal solution and propose a hybrid genetic algorithm with a two-stage dispatching heuristic represented by a simple chromosome. The performance of the proposed genetic algorithm (GA) is compared with GAs with two types of chromosome representations using randomly generated test instances.