Abstract:This paper aims at minimizing makespan of parallel batch processing machines with non-identical job sizes. All the jobs are grouped into batches within the restraint of machines' capacity and then scheduled on the machines. First, a mixed integer programming model is summarized for this problem and a lower bound is proposed. Then an FF-LPT rule is addressed to form batches and assign batches on machines. And an estimation of distribution algorithm (EDA) with four different update mechanism is proposed. The performance of proposed algorithm is evaluated by comparing with a simulated annealing algorithm (SA) and a genetic algorithm (GA). The experimental results indicate that the effectiveness of proposed algorithm.