Author: Tamer EREN, Ertan GÜNER
Publishing Date: 2006
E-ISSN: 2147-9364
Volume 21 Issue 1_2
ABSTRACT:
In this study bicriteria identical two parallel machine scheduling problem is considered. The objective function of the problem is minimization of the weighted sum of completion time and maximum tardiness. Total completion time and maximum tardiness are widely used performance measures in scheduling literature. An integer programming model with 2/2/32/ 23 nnn ++ variables and 23n constraints (where n is the number of jobs) is developed for the problem which belongs to NP-hard class. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 20 jobs can be solved. A random search method and tabu search based heuristic algorithms (Tabu I, Tabu II and Tabu III) are presented to solve large size problems. To improve the performance of tabu search algorithms the sequences found from the well known dispatching rules are taken as an initial solution of tabu search algorithms. According to computational results the tabu search algorithm is effective in finding problem solutions with up to 1000 jobs.
Key Words: Identical parallel machine; bicriteria; integer programming; heuristic methods.