Exact and Approximation Approaches for Solving Multiple Objective Function | ||
| Al-Mustansiriyah Journal of Science | ||
| Article 1, Volume 27, Issue 3, July 2016, Pages 89-97 | ||
| Author | ||
| Tariq Salih Abdul-Razaq | ||
| Abstract | ||
| In this paper we consider the problem of multi-criteria scheduling n jobs on a single machine to minimize the sum of the total flow times, maximum earliness and maximum tardiness (i.e. to minimize the Multiple Objective Function (MOF) defined by ∑_j▒C_j +E_max+T_max). The main contribution is a Branch and Bound (BAB) algorithm to find optimal solution. The BAB method uses dominance rules to reduce the number of sequences that must be considered. Since this problem is NP-hard, we propose Tree Type Heuristic (TTH) Method and Variable Neighborhood Descent (VND) algorithm to solve the problem efficiently. Also we introduce some special cases of the problem to find optimal solution. We discuss and modify algorithms to find optimal and near optimal solutions to our scheduling problem. The exact algorithms produce optimal solutions, but its running time cannot be bounded from above by a polynomial in the size of an instance for NP-hard problem. Approximation algorithms produce solutions in relatively little computation time, but their solutions need not be optimal. Computational results show that the approximate algorithms (TTH and VND) are able to solve instances of our problem for large sizes. | ||
|
Statistics Article View: 111 PDF Download: 32 |
||