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

Authors: Wisut Supithak, Karn Plongon

Addresses: Department of Industrial Engineering, Faculty of Engineering, Kasetsart University, Chatujuk, Bangkok, Thailand. ' Department of Industrial Engineering, Faculty of Engineering, Kasetsart University, Chatujuk, Bangkok, Thailand

Abstract: 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.

Keywords: memetic algorithms; parallel machine scheduling; non-identical machines; earliness; tardiness.

DOI: 10.1504/IJMTM.2011.038481

International Journal of Manufacturing Technology and Management, 2011 Vol.22 No.1, pp.26 - 38

Published online: 27 Nov 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article