Pareto Optimal Solutions of the Biobjective Bottleneck Assignment Problem

In this paper we describe the computation of all Pareto optimal solutions of a fundamental biobjective variant of the assignment problem (AP). The examined problem is the MAXMIN-MINMAX AP in which both criteria are non-linear bottleneck functions: maximal capacity and minimal time. We introduce the main algorithm that solves the biobjective bottleneck AP, along with its helper functions that are needed for its implementation. We prove the correctness of the algorithms their computational complexity. The presented method is applicable to majority of the MAXMIN-MINMAX versions of the AP, and with few modifications can be adopted to solve the other standard biobjective bottleneck APs.