F Firouzi jahantigh - Department of Industrial Engineering, University of Sistan and Baluchestan
M Karimi-Nasab - Department of Industrial Engineering, Iran University of Science and Technology
A Zareei - Department of Industrial Engineering, Iran University of Science and Technology

This paper addresses single machine bi-criteria scheduling problem with the aim of minimizing: total completion time and total weighted tardiness simultaneously. Shortest processing time (SPT) rule results in optimal sequence for the first objective while the second objective, total weighted tardiness, is proved to be NP-hard.Therefore an algorithm based on Tabu search mechanism is developed. Since LPmetric method is a rigorous multi-objective technique for making a combined dimensionless objective, it is used to navigate the search direction of Tabu Search. In this way, we can reach to some of solutions that are compatible in decision maker’s opinion while overcoming the issue of problem complexity. Finally for testing the efficiency of the proposed approach, some of the test problems are solved.

Single machine Scheduling, LP-metric, Tabu Search, NP-hard