Abstract
This study solves the static unrelated parallel machine problem with uncertain processing time. We assume due date of each job is known and deterministic and the processing time of each job is normally distributed with known parameters of mean and variance . The objective is to minimize average expected tardiness. By using a proposed formula, the evaluation of a schedule with uncertain processing times will not much longer than that of a schedule with deterministic processing times. Six methods are used to generate an initial solution and four search algorithms (tabu search, simulated annealing, genetic algorithm and memetic algorithm) are applied to solve the scheduling problem. Experimental designs and statistical methods are used to evaluate and analyze the performance of initial solution methods and search algorithms. The results reveal that ATC performs best generating in initial solution and tabu search performs the best in search algorithms.