Abstract: | In this article we consider a multiperiod assignment problem where the assignment cost of assigning job i to machine j varies from one time period to the next. A start-up cost is incurred whenever the job processed 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. Our computational results show that our 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. © 1993 John Wiley & Sons, Inc. |