Makespan Minimization for Parallel Machines Environment with Machine Dependent Processing Time by Using PBIL Combined with Local Search

Pensiri Sompong, Sungkom Srisomporn

Abstract

Population-based incremental learning algorithm (PBIL) is proposed to solve parallel machines scheduling problem with machine dependent processing time. The initial population of proposed algorithm is created based on probability vector resulting from the solution obtained from applying shortest processing time (SPT) dispatching rule for parallel machines to represent the jobs assigned on the machines. Local search is performed during the process to move a job to an appropriate machine that makespan is minimized. The performance of the algorithm is illustrated by numerical examples. The solutions obtained from PBIL are compared to the solution from SPT. The results show that the assignment of jobs by using PBIL combined with local search can reduce makespan and it is suitable for solving parallel machines scheduling problem with machine dependent processing time.