Using PBIL to Minimize Makespan for Parallel Machines Scheduling Problem with Job Sequence Dependent Setup Time

Pensiri Sompong

Abstract

Parallel machines scheduling problem with job sequence dependent setup time is studied. The objective is to determine job schedule in which makespan is minimum. The problem is divided into two parts, assigning n independent jobs to m parallel machines and sequencing jobs on each machine. Population-based incremental learning (PBIL) algorithm is used to assign jobs to machines and SPT regarding sequence dependent setup time is then applied to determine sequence of job on each machine. The performance and efficiency of proposed algorithm are shown by the experiments. The solutions obtained from applying PBIL combined with SPT are compare to solutions obtained from using SPT for parallel machines. The average relative percentage deviation is 13.55% indicating good performance. From the study results, it is shown that the proposed algorithm is useful and efficient for parallel machines scheduling problem with job sequence dependent setup time.