DECOMPOSITION METHODS FOR SCHEDULING SEMICONDUCTOR TESTING FACILITIES

We present decomposition procedures for scheduling semiconductor testi ng facilities. These facilities are characterized by the presence of d ifferent types of work centers, some of which have sequence-dependent setup times and some parallel identical machines. We exploit the struc ture of the routings in semiconductor testing to develop tailored deco mposition procedures that decompose the shop into a number of work cen ters that are scheduled using specialized procedures. Extensive comput ational experiments show that these procedures significantly outperfor m existing methods in reasonable CPU times. These results indicate tha t decomposition methods can be successfully applied to complex schedul ing problems of the type addressed in this paper, as well as the class ical job shop problems addressed in previous research.