Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives

Nervousness in machine assignments during rescheduling can cause problems for the implementation of a scheduling system. This paper examines rescheduling due to the arrival of new jobs to the system. Parallel machine scheduling problems with stepwise increasing tardiness cost objectives, non-zero machine ready times, constraints that limit machine reassignments, and machine reassignment costs are considered. Simulation experiments and individual scheduling problems indicate that nervousness can be controlled at a low cost in some parallel machine scheduling environments. The rescheduling problems in the simulation are solved with a branch-and-price algorithm. Significant gains in schedule stability can be achieved by selecting the alternative optimal solution with the fewest machine reassignments.