AbstractThe assignment problem (AP) and bottleneck assignment problem (BAP) are well studied in operational research literature. In this paper we consider two related problems which simultaneously generalize both AP and BAP. Unlike AP and BAP, these generalizations are strongly NP-complete. We propose two heuristics to solve these generalized problems: one based on a greedy principle and the other based on tabu search. Computational 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.