Solving the multiperiod assignment problem with start-up costs using dual ascent

This article considers a multiperiod assignment problem where the assignment cost of assiging job i to machine j varies from one time period to the next. A start-up cost is incurred whenever the job processes by a machine in the current time period is different from the one processed in the previous time period. This problem is modeled as an integer programming problem for which a dual ascent approximate procedure is developed. The present computational results show that the procedure outperforms the more common Lagrangian-relaxation-based subgradient procedure by a significant margin. It is also found to be faster than MPSX/370 by many orders of magnitude.