A Branch-Bound Algorithm to Minimize the Maximum Tardiness with Minimum Number Tardy

Multi-criteria scheduling problems play more and more important roles in solving complicated problems appearing in economy, management,engineering,military affairs and society etc.In 2007,a paper proved that the two multi-criteria scheduling problems 1‖(ΣC_j/ΣU_j) or 1‖(ΣT_j/ΣU_j) to minimize the total completion time or the total tardiness with minimum number of tardy jobs are NP hard. However,till now,the computational complexity of the multi-criteria scheduling problem 1]l(TmaJ~Uj) have still not been known.In this paper,the authors propose a branch-bound algorithm for the problem 1‖(T_(max)/ΣU_j).They find its several properties.Through them,they get good upper and lower bounds,and so get the optimal solution more quickly.