REDUCTION OF MULTICRITERIA SCHEDULING PROBLEMS TO BICRITERIA SCHEDULING PROBLEMS

Abstract

        Most multicriteria scheduling problems are NP-hard, while the optimal or approximate polynomial algorithms have been obtained for many single criterion and bicriteria scheduling problems. Therefore, heuristic methods like descent, simulated annealing, tabu search and genetic algorithms that produce approximate solutions are  usually employed in solving multicriteria problems. This article presents the possibility of reducing multicriteria scheduling problems to bicriteria scheduling problems to make them solvable with optimal polynomial time  algorithms. The solution for the reduced bicriteria scheduling problems will also solve the parent multicriteria problem without compromising its linear composite objective function.