Algorithm for Solving Parallel Machines Scheduling Problem to Minimize Earliness and Tardiness Costs
Article Sidebar
Main Article Content
Abstract
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
E-mail: pensiri.so@ku.th
Article Details
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
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.
Bauman, J. and Józefowska, J., 2006. Minimizing the earliness-tardiness costs on a single machine. Computers & Operations Research, 33(11), 3219-3230.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Baluja, S., 1994. Population-based Incremental Learning: A Method forIintegrating Genetic Search Based Function Optimization and Competitive Learning. [online] Available at: https://www.ri.cmu.edu/pub_files/pub1/baluja_shumeet_1994_2/baluja_shumeet_1994_2.pdf
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.
