Galoitica: Journal of Mathematical Structures and Applications
Journal DOI
2834-5568ISSN (Online)
Volume 10 , Issue 2 , PP: 44-51, 2024 | Cite this article as | XML | Html | PDF | Full Length Article
Hussein Abdullah Jaafar 1 * , Hanan Ali Chachan 2
Doi: https://doi.org/10.54216/GJMSA.0100204
In this research, the issue of scheduling n-jobs on one-machine is represented to minimize Five-Objectives-Function (FOF), for finding approximation solutions for the sum of completion time, total tardiness, total earliness, number of late jobs and late work with release date, this issue denoted by: Hanan and Hussein used a branch and bound technique (B-a-B) to discovery an optimal solution path. Computational results showed the (B-a-B) technique was efficient in solving issues with up to (16- jobs). Because our issue is of a very difficult type (NP-hard), we suggest local search algorithms to discovery near optimal solution. The execution of local search techniques can be tested on large group of test issues. Computational results showed with up to (30000 jobs) in acceptable time.
Branch and Bound (B-a-B) , Local Search (LS) , Simulated Annealing (SA) , Genetic algorithm (GA).
[1] Chen, B., Chris N. P, and Gerhard, J. W. "A review of machine scheduling: Complexity, algorithms and Approximability," Handbook of combinatorial optimization. Springer, Boston, MA, (1998). 1493-1641.
[2] Michael, L. P. " Scheduling: theory, algorithms, and systems". Fifth Edition, (2016).
[3] Walser, J. P. "Integer optimization by local search: a domain-independent approach". Springer-Verlag, (1999).
[4] Nagar A., Haddock J. and Heragu S.,(1995). Multiple and Bi-Criteria
Scheduling a Literature Survey, Eur. J.OPI. Res. 1:88-104.
[5] HA Chachan, HA Jaafar. "Exact Solutions for Minimizing cost Function with Five Criteria and Release Dates on Single Machine". Ibn AL-Haitham Journal For Pure and Applied Science, 2020. Sci. 33 (3).
[6] Chu, C, and Portmannm M.C. "Some new efficient methods to solve the n/1/ri/∑Ti scheduling problem", European journal of operational research 58.3 (1992): 404-413.
[7] Dunham, B., Fridshal, D., Fridshal, R., & North, J. H. Design by natural selection. In Form and Strategy in Science. (1964). 306-311.
[8] Sörensen, K., and Fred, W. G. "Metaheuristics." Encyclopedia of operations research and management science (2013): 960-970.
[9] Kirkpatrick, S., Gelatt, C. D., & Vecchi, M.P. "Optimization by simulated annealing." science 220.4598 (1983): 671-680.
[10] Haupt, R. L., and Sue, E. H. "Practical genetic algorithms." .SECOND EDITION, (2004).
[11] Holland, J. "Adaptation in natural and artificial systems: an introductory analysis with application to biology." Control and artificial intelligence (1975).
[12] Goldberg, D. E., and Holland, J.H. "Genetic algorithms and machine learning." Machine learning 3.2 (1988): 95-99.
[13] Baúto, J., Neves,R., and Horta, N. "Parallel Genetic Algorithms for Financial Pattern Discovery Using GPUs". Springer International Publishing, (2018).
