Hybrid genetic algorithm to minimize scheduling cost with unequal and job dependent earliness tardiness cost

Prasad Bari; Prasad Karande; Vaidehi Bag

doi:10.4995/ijpme.2024.19277

Authors

Prasad Bari Fr. C. Rodrigues Institute of Technology https://orcid.org/0000-0002-6257-8196
Prasad Karande Veermata Jijabai Technological Institute https://orcid.org/0000-0002-2840-6120
Vaidehi Bag Fr. C. Rodrigues Institute of Technology

DOI:

https://doi.org/10.4995/ijpme.2024.19277

Keywords:

Earliness, Tardiness, Cost, Common Due Date, Genetic Algorithm

Abstract

This article presents two combinatorial genetic algorithms (GA), unequal earliness tardiness-GA (UET-GA) and job-dependent earliness tardiness-GA (JDET-GA) for the single-machine scheduling problem to minimize earliness tardiness (ET) cost. The sequence of jobs produced in basic UET and JDET as a chromosome is added to the random population of GA. The best sequence from each epoch is also injected as a population member in the subsequent epoch. The proposed improvement seeks to achieve convergence in less time to search for an optimal solution. Although the GA has been implemented very successfully on many different types of optimization problems, it has been learnt that the algorithm has a search ability difficulty that makes computations NP-hard for types of optimization problems, such as permutation-based optimization problems. The use of a plain random population initialization results in this flaw. To reinforce the random population initialization, the proposed enhancement is utilized to obtain convergence and find a promising solution. The cost is further significantly lowered offering the due date as a decision variable with JDET-GA. Multiple tests were run on well-known single-machine benchmark examples to demonstrate the efficacy of the proposed methodology, and the results are displayed by comparing them with the fundamental UET and JDET approaches with a notable improvement in cost reduction.

Downloads

Download data is not yet available.

References

Akande, S., & Ajisegiri, G. (2022). Three classes of Earliness-Tardiness (E/T) scheduling problems. Fuel Communications, 10, 100047. https://doi.org/10.1016/j.jfueco.2021.100047

Alidaee, B., Li, H., Wang, H., & Womer, K. (2021). Integer programming formulations in sequencing with total earliness and tardiness penalties, arbitrary due dates, and no idle time: A concise review and extension. Omega (United Kingdom), 103, 102446. https://doi.org/10.1016/j.omega.2021.102446

Allaoua, H., & Osmane, I. (2010). Variable parameters lengths genetic algorithm for minimizing earliness-tardiness penalties of single machine scheduling with a common due date. Electronic Notes in Discrete Mathematics, 36(C), 471-478. https://doi.org/10.1016/j.endm.2010.05.060

Arık, O. A. (2020). Comparisons of metaheuristic algorithms for unrelated parallel machine weighted earliness/tardiness scheduling problems. Evolutionary Intelligence, 13(3), 415-425. https://doi.org/10.1007/s12065-019-00305-7

Arık, O. A., Schutten, M., & Topan, E. (2022). Weighted earliness/tardiness parallel machine scheduling problem with a common due date. Expert Systems with Applications, 187. https://doi.org/10.1016/j.eswa.2021.115916

Baker, K. R., & Scudder, G. D. (1990). Sequencing with earliness and tardiness penalties. A review. Operations Research, 38(1), 22-36. https://doi.org/10.1287/opre.38.1.22

Bari, P., & Karande, P. (2022a). Cost Minimization in a Scheduling Problem with Unrestricted and Restricted Common Due Date. Recent Advances in Industrial Production. Lecture Notes in Mechanical Engineering. Springer, Singapore, 269-278. https://doi.org/10.1007/978-981-16-5281-3_25

Bari, P., Karande, P., & Menezes, J. (2022b). Simulation of Job Sequencing for Stochastic Scheduling With a Genetic Algorithm. Operational Research in Engineering Sciences: Theory and Applications, 5(3), 17-39. https://doi.org/10.31181/060722075b

Beyranvand, M. S., Peyghami, M. R., & Ghatee, M. (2012). On the quadratic model for unrelated parallel machine scheduling problem with restrictive common due date. Optimization Letters, 6(8), 1897-1911. https://doi.org/10.1007/s11590-011-0385-0

Biskup, D., & Feldmann, M. (2001). Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Computers and Operations Research, 28(8), 787-801. https://doi.org/10.1016/S0305-0548(00)00008-3

Branco, R. M., Coelho, A. S., & Mayerle, S. F. (2016). Hybrid genetic algorithms: solutions in realistic dynamic and setup dependent job-shop scheduling problems. International Journal of Production Management and Engineering, 4(2), 75. https://doi.org/10.4995/ijpme.2016.5780

Carlier, J., Hermès, F., Moukrim, A., & Ghédira, K. (2010). Exact resolution of the one-machine sequencing problem with no machine idle time. Computers and Industrial Engineering, 59(2), 193-199. https://doi.org/10.1016/j.cie.2010.03.007

Chen, Y. W., Lu, Y. Z., Ge, M., Yang, G. K., & Pan, C. C. (2012). Development of hybrid evolutionary algorithms for production scheduling of hot strip mill. Computers and Operations Research, 39(2), 339-349. https://doi.org/10.1016/j.cor.2011.04.009

Gupta, A., & Kumar, S. (2016). Flow shop scheduling decisions through Techniques for Order Preference by Similarity to an Ideal Solution (TOPSIS). International Journal of Production Management and Engineering, 4(2), 43. https://doi.org/10.4995/ijpme.2016.4102

Hatami, S., Ruiz García, R., & Romano, C. A. (2015). The Distributed Assembly Parallel Machine Scheduling Problem with eligibility constraints. International Journal of Production Management and Engineering, 3(1), 13. https://doi.org/10.4995/ijpme.2015.3345

Irani, S., & Pruhs, K. (2005). Algorithmic problems in power management, ACM SIGACT News, 36(2), 63-76. https://doi.org/10.1145/1067309.1067324

Kanet, J. J. (1981). Minimizing the average deviation of job completion times about a common due date. Naval Research Logistics, 28(4), 643-651. https://doi.org/10.1002/nav.3800280411

Kanet, J. J., & Sridharan, V. (2000). Scheduling with inserted idle time: problem taxonomy and literature review. Operations Research, 48(1), 99-110. https://doi.org/10.1287/opre.48.1.99.12447

Khoshjahan, Y., Najafi, A. A., & Afshar-Nadjafi, B. (2013). Resource constrained project scheduling problem with discounted earliness-tardiness penalties: Mathematical modeling and solving procedure. Computers and Industrial Engineering, 66(2), 293-300. https://doi.org/10.1016/j.cie.2013.06.017

Liaw, C. F. (1999). A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem. Computers and Operations Research, 26(7), 679-693. https://doi.org/10.1016/S0305-0548(98)00081-1

M'Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers and Operations Research, 34(10), 3126-3142. https://doi.org/10.1016/j.cor.2005.11.021

Ow, P. S., & Morton, T. E. (1989). The single machine early/tardy problem. Management Science, 35(2), 177-191. http://www.jstor.org/stable/2631910 https://doi.org/10.1287/mnsc.35.2.177

Oyetunji, E. O. (2009). Some common performance measures in scheduling problems: Review article. Research Journal of Applied Sciences, Engineering and Technology, 1(2), 6-9.

Plateau, M. C., & Rios-Solis, Y. A. (2010). Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations. European Journal of Operational Research, 201(3), 729-736. https://doi.org/10.1016/j.ejor.2009.03.049

Raghavan, V. A., Yoon, S. W., & Srihari, K. (2018). A modified Genetic Algorithm approach to minimize total weighted tardiness with stochastic rework and reprocessing times. Computers and Industrial Engineering, 123, 42-53. https://doi.org/10.1016/j.cie.2018.06.002

Rolim, G. A., & Nagano, M. S. (2020). Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review. Computers and Industrial Engineering, 149. https://doi.org/10.1016/j.cie.2020.106803

Schaller, J., & Valente, J. M. S. (2013). A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. International Journal of Production Research, 51(3), 772-779. https://doi.org/10.1080/00207543.2012.663945

Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155(13), 1643-1666. https://doi.org/10.1016/j.dam.2007.02.003

Stanković, A., Petrović, G., Ćojbašić, Ž., & Marković, D. (2020). An application of metaheuristic optimization algorithms for solving the flexible job-shop scheduling problem. Operational Research in Engineering Sciences: Theory and Applications, 3(3), 13-28. https://doi.org/10.31181/oresta20303013s

Wagner, B. J., Davis, D. J., & Kher, H. V. (2002). The production of several items in a single facility with linearly changing demand rates. Decision Sciences, 33(3), 317-346. https://doi.org/10.1111/j.1540-5915.2002.tb01647.x

Woodruff, D. L., & Spearman, M. L. (1992). Sequencing and batching for two classes of jobs with deadlines and setup times. Production and Operations Management, 1(1), 87-102. https://doi.org/10.1111/j.1937-5956.1992.tb00341.x

Yuce, B., Fruggiero, F., Packianather, M. S., Pham, D. T., Mastrocinque, E., Lambiase, A., & Fera, M. (2017). Hybrid Genetic Bees Algorithm applied to single machine scheduling with earliness and tardiness penalties. Computers and Industrial Engineering, 113, 842-858. https://doi.org/10.1016/j.cie.2017.07.018