Memetic algorithm for non-identical parallel machines scheduling problem with earliness and tardiness penalties

We consider the problem of determining the production schedule of n jobs on m non-identical parallel machines so that the sum of earliness and tardiness penalties is minimised. In the problem, each job has its own due date, earliness penalty, and tardiness penalty. To reduce the size of possible solution set, the problem is reduced to the job sequencing problem. The evolutionary procedures are developed, as the search in the global optimisation phase, to properly assign jobs to each machine and determine job sequence. In the local optimisation phase, the optimal timing algorithm is applied to determine the best schedule of each job sequence. In order to evaluate the performance of the memetic algorithm (MA) at different penalty cost rate and problem size, the solution from the heuristic is compared with the optimal solution obtained from the simple branch and bound method. The results show that the MA is promising.