A simulation study of methodologies for controlling nervousness in parallel machine scheduling problems

Nervousness in machine assignments during rescheduling can cause problems for the implementation of a scheduling system. To control nervousness, this research adds machine reassignment costs and constraints that limit the number of machine reassignments to the scheduling formulation. Simulation experiments indicate that nervousness can be controlled at a low cost in some parallel machine scheduling environments. Significant gains in schedule stability can be achieved by just selecting the alternative optimal solution with the fewest machine reassignments.; 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 optimally solved using a branch and price procedure in the simulation experiments. The algorithm is an extension of Chen and Powell's (1999) algorithm for solving the parallel machine scheduling problem with a weighted number of late jobs scheduling objective. The algorithm employs a preemption-based lower bound and custom branch logic to quickly solve the scheduling problem in the simulation experiments. The algorithm is effective at solving large scheduling problems with 130 jobs and 10 machines. The scheduling algorithm can find the set of solutions that are efficient for the objectives of number of machine reassignments and tardiness cost as measured by a stepwise increasing tardiness cost objective. The solution times for optimally solving the scheduling problems are very competitive as compared to prior research on parallel machine scheduling with tardiness related objectives.