International Journal of Nonlinear Analysis and Applications
Search method for solving multicriteria scheduling problem
Document Type : Research Paper
Author
Department of Mathematics, College of Science, University of Al-Mustansiriyah, Bagdad, Iraq
Abstract
Our research includes studying the case $ 1 // F(\sum U_i ,\sum Ti ,T_{max})$ minimized the cost of a three-criteria objective function on a single machine for scheduling n jobs. and divided this into several partial problems and found simple algorithms to find the solutions to these partial problems and compare them with the optimal solutions. This research focused on one of these partial problems to find minimize a function of sum cost of $ (\sum U_i) $ sum number of late job and $ (\sum Ti) $ sum Tardiness and $ (T_{max} ) $ the Maximum Tardiness for n job on the single machine, which is NP-hard problem, first found optimal solutions for it by two methods of Complete Enumeration technique(CEM) and Branch and Bounded ((BAB)). Then use some Local search methods(Descent technique(DM), Simulated Annealing (SA) and Genetic Algorithm (GA)), Develop algorithm called ((A)) to find a solution close to the optimal solution. Finally, compare these methods with each other.
Keywords
[2] I. T Abbas, The Performance of Multicriteria Scheduling in one Machine, M.Sc tThesis, Univ. of AlMustansiriyah, College of Science, Dept. of Mathematics, 2009.
[3] T. S. Abdul-Razaq, Z. M. Ali, Minimizing the Total Completion Time, the Total Tardiness and the Maximum Tardiness, Ibn Al-Haitham J. Pure Appl. Sci. 28(2) (2015) 155–170.
[4] T.S. Abdul-Razaq and A.O. Akram, Local search algorithms for multi-criteria single machine scheduling problem, Ibn Al-Haitham J. Pure Appl. Sci. (2017) 436-451.
[5] M.G. Ahmed, A single machine scheduling problem to minimize the sum of total Completion times and total Late works, Res. Al-Mustansiriyah J. Sci. 23(7) (2012) 117–130.
[6] H. Ali, Exact and Heuristic Algorithms for Solving Combinatorial Optimization Problems, PH.D. Thesis, Department of Mathematics, College of Science, University of Al-Mustansiriyah, 2017.
[7] S.S. Al-Assaf, Solving Multiple Objectives Scheduling Problems, M.Sc. Thesis, Univ. of Al-Mustansiriyah, College of Science, Dept. of Mathematics, 2007.
[8] M.K. Al Zuwaini, S.K. Al Saidy and T. S. Abdul-Razaq, Comparison study for some local search methods for multiple objective function in a single machine scheduling problem, J. Basrah Res. (Science) 37(4) (2011) 103–113.
[9] N. Anang, M.S. Hamid and W.M.W. Muda, Simulation and modelling of electricity usage control and monitoring system using rhing speak, Baghdad Sci. J. 18 (2021) 907–927.
[10] H. Chachan and A. Hameed, Exact methods for solving multi objective problem on single machine scheduling, Iraqi J. Sci. 60 (2019) 1802–1813.
[11] A. Gupta and R.P. Mahapatra, Multifactor algorithm for test case selection and ordering, Baghdad Sci. J. 18 (2021) 1056–1075.
[12] J.A. Hoogeveen, Multicriteria Scheduling, Eur. J. Oper. Res. 167 (2005) 592–623.
[13] C. Junheng, C. Feng, L. Ming, W. Peng and X. Weili, Bi-criteria single machine batch scheduling with machine on/off switching under time-ofuse tariffs, Comput. Ind. Eng. 112 (2017) 721–734.
[14] M.E. Kurz and S. Canterbury Minimizing total flow time and maximum earliness on a single machine using multiple measures of fitness, Genetic and Evolutionary Computation Conf. (2005) pp. 803-809.[15] A.A. Mahmood, Approximation solution for multicriteria scheduling, Prob. Res. Al-Rafidain University College Sci. 1(34) (2014) 161–179.
[16] A.A. Mahmood and T.S. Abdul-Razaq, Exact algorithm for minimizing the sum of total late work and maximum late work problem, Res. Diyala J. Pure Sci. 10 (2014) 39–50.
[17] A.A. Mahmood Al-Nuaimi, Local search algorithms for multiobjective scheduling problem, Al Rafidain J. University College Sci. (1681-6870) 2015201-217.
[18] A. Muthiah, R. Rajkumar and B. Muthukumar, Minimizing makespan in job shop scheduling problem using genetic algorithm, Appl. Mech. Mater. 813-814 (2015) 1183–1187.
[19] E.O. Oyetunji and A.E. Oluleye, Heuristics for minimizing total completion time and number of tardy jobs simultaneously on single machine with release time, Res. J. Appl. Sci.3 (2008) 147–152.
[20] M. Reisi-Nafchi and G.A. Moslehi, Hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem, Appl. Soft. Comput. 33 (2015) 37–47.
[21] W. Shao and Z. Shao, A Pareto-based estimation of distribution algorithm for solving multiobjective distributed no-wait flow-shop scheduling problem with sequence dependent setup time, IEEE. Trans. Autom. Sci. Eng. 16 (2019) 1344–1360.
[22] N. Tyagi, R.P. Tripathi and A.B. Chandramouli, Single machine scheduling model with total tardiness problem, Indian J. Sci. Technol. 9(37) (2016) 1–14.
)
Volume 13, Issue 1
March 2022Pages 1709-1720
- Receive Date: 11 March 2021
- Revise Date: 19 April 2021
- Accept Date: 06 May 2021