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 Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants 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.
Here is the link for download: Copyright transfer form.pdf
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.