Algorithm for Solving Parallel Machines Scheduling Problem to Minimize Earliness and Tardiness Costs

Main Article Content

Pensiri Sompong*


Algorithm for parallel machines scheduling problem to minimize the earliness and tardiness costs is proposed in this study. The problem is associated with the assignment of jobs to machines and determination of staring time for each job in a given sequence. Population-based incremental learning (PBIL) algorithm is used to allocate the jobs to machines. The optimal timing algorithm based on the minimum block cost function calculation is then employed to decide the starting time of jobs on each machine. To illustrate the performance of proposed algorithm, numerical examples generated randomly are tested. The numerical results obtained from PBIL combined with optimal timing algorithm called PBILOTA are compared to EDDPM (Earliest Due Date for Parallel Machines) to indicate the decrease in penalty cost. From the experimental results, it is shown that PBILOTA is an efficient algorithm for solving parallel machines scheduling problem with earliness-tardiness costs minimization.


Keywords: population-based incremental learning algorithm; scheduling; parallel machines; earliness; tardiness

*Corresponding author: Tel.: +66 42 72 5033 Fax: +66 42 72 5034



Download data is not yet available.

Article Details

Research Articles


[1] Lee, C.Y. and Choi, J.Y., 1995. A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights. Computers & Operations Research, 22(8), 857-869.
[2] Bauman, J. and Józefowska, J., 2006. Minimizing the earliness-tardiness costs on a single machine. Computers & Operations Research, 33(11), 3219-3230.
[3] Kedad-Sidhoum, S. and Sourd, F., 2010. Fast neighborhood search for the single machine earliness-tardiness scheduling problem. Computers & Operations Research, 37(8), 1464-1471.
[4] Kianfar, K. and Moslehi, G., 2012. A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties. Computers & Operations Research, 39(12), 2978-2990.
[5] Keshavarz, T., Savelsbergh, M. and Salmasi, N., 2015. A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties. Applied Mathematical Modelling, 39(20), 6410-6424.
[6] Rosa, B.F., Souza, M.J.F., de Souza, S.R., de França Filho, M.F., Ales, Z. and Michelon, P., 2017. Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties. Computers & Operations Research, 88, 203-215.
[7] Kayvanfar, V., Komaki, GH.M., Aalaei, A. and Zandieh, M., 2014. Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing time. Computers & Operations Research, 41, 31-43.
[8] Zeidi, J.R. and Mohammad Hosseini, S., 2015. Scheduling unrelated parallel machines with sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 81(9-12), 1487-1496.
[9] Alvarez-Valdes, R., Tamarit, J.M. and Villa, F., 2015. Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristic. Computers & Operations Research, 54, 1-11.
[10] Hung, Y.-F., Bao, J.-S. and Chen, Y.-E., 2017. Minimizing earliness and tardiness costs in scheduling jobs with time windows. Computers & Industrial Engineering, 113, 871-890.
[11] Wu, R., Guo, S. and Li, X., 2017, Unrelated parallel machine scheduling with job rejection and earliness-tardiness penalties. Proceedings of the 36th Chinese Control Conference, Dalian, China, July 26-28, 2017, 2846-2851.
[12] Baluja, S., 1994. Population-based Incremental Learning: A Method forIintegrating Genetic Search Based Function Optimization and Competitive Learning. [online] Available at:
[13] Joo, C.M. and Kim, B.S., 2015. Hybrid genetic algorithms with dispatching rules for unrelated parallel machines scheduling with setup time and production availability. Computers & Industrial Engineering, 85, 102-109.