CATEGORIZED ASSIGNMENT SCHEDULING - A TABU SEARCH APPROACH

The assignment problem (AP) and bottleneck assignment problem (BAP) ar e well studied in operational research literature. In this paper we co nsider two related problems which simultaneously generalize both AP an d BAP. Unlike AP and BAP, these generalizations are strongly NP-comple te. We propose two heuristics to solve these generalized problems: one based on a greedy principle and the other based on tabu search. Compu tational results are presented which show that these heuristics, when used together, produce good quality solutions. Our adaptation of tabu search also gives some new insight into the application of tabu search on permutation problems.