International Journal of Nonlinear Analysis and Applications

Solving multi-objectives function problem using branch and bound and local search methods

Document Type : Research Paper

Authors

Mathematics Dept, Mustansiriyah University, College of Science/ Baghdad, Iraq

Abstract

In this paper we consider $1//\sum^n_{j=1}{(E_j+T_j+C_j+U_j+V_j)}$ problem, the discussed problem is called a Multi objectives Function (MOF) problem, As objective is to find a sequence that minimizes the multiple objective functions, the sum earliness, the tardiness, the completion time, the number of late jobs and the late work. The NP-hard nature of the problem, hence the existence of a polynomial time method for finding an optimal solution is unlikely. This complexity result leads us to use an enumeration solution approach. In this paper we propose a branch and bound method to solve this problem. Also, we use fast local search methods yielding near optimal solution. We report on computation experience; the performances of exact and local search methods are tested on large class of test problems.

Keywords

[1] M. Rajabzadeh, H. Vahdani, Z. Arabasadi, Single machine scheduling with different types of transportation facilities in batch delivery system, CIE44 & IMSS14 Proceedings, 14-16 October 2014, Istanbul / Turkey, Pages: 1441-1450.
[2] C. A. C. Coello, G. B. Lamont, Applications of multi-objective evolutionary algorithms, Vol.1, World Scientific, 2004.
[3] S. Garcia, C. T. Trinh, Comparison of multi-objective evolutionary algorithms to solve the modular cell design problem for novel biocatalysis, Processes, 7(6) (2019) 361.
[4] K. Steinh¨ofel, A. Albrecht, C. K. Wong, An experimental analysis of local minima to improve neighbourhood search, Computers & Operations Research, 30(14)(2003) 2157-2173.
[5] H. A. Mohammed, Exact and Heuristic Algorithms for Solving Combinatorial Optimization Problems, Ph.D. Thesis, Mustansiriyah University, College of Science, Dept. of Mathematics 2017.
[6] H. A. Chachan, A. S. Hameed, Exact Methods for Solving Multi-Objective Problem on Single Machine Scheduling, Iraqi Journal of Science, (2019) 1802-1813.
[7] T. S. Abdul-Razaq, A. O. Akram, Local Search Algorithms for Multi-Criteria Single Machine Scheduling Problem, Ibn AL Haitham Journal for Pure and Applied Science, (2018) 436-451.
[8] T. S. Abdul-Razaq, F. H. Ali, Algorithms for Scheduling a Single Machine to Minimize Total Completion Time and Total Tardiness. Basrah Journal of Science, 34(A (2)) (2016) 113-132.
[9] T.S. Abdul-Razaq, H. M. Motair, Solving Composite Multi-objective Single Machine Scheduling Problem Using Branch and Bound and Local Search Algorithms. Al-Mustansiriyah Journal of Science, 28(3) (2018) 200-208.
[10] L. P. Michael, Scheduling: theory, algorithms, and systems, Springer 2018.
[11] E. L. Lawler, Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19 (5) (1973) 544-546.
[12] A. A. Mahmood, Solution procedures for scheduling job families with setups and due dates, Doctoral dissertation, M. Sc. Thesis, University of AL-Mustansiriyah, College of Science, Dept. of Mathematics 2001.
[13] W. E. Smith, Various optimizer for single-stage production, Naval Research Logistics Quarterly, 3(1-2) (1956) 59-66.
[14] I. M. Alharkan, Algorithms for sequencing and scheduling, Industrial Engineering Department, King Saud University, Riyadh, Saudi Arabia 2005.
[15] J. R. Jackson, Scheduling a production line to minimize maximum tardiness, management science research project 1955.
[16] J. A. Hoogeveen, S. L. van de Velde, Polynomial-time algorithms for single-machine multicriteria scheduling, Department of Operations Research, Statistics, and System Theory [BS], (R 9008) (1990).
[17] C. P. Tomazella, M. S. Nagano, A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flow shop scheduling problem. Expert Systems with Applications, 158 (2020) 113556.
[18] H. He, H. Daume III, J. M. Eisner, Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27(2014) 3293-3301.
[19] J. N. Gupta, K. Hennig, F. Werner, Local search heuristics for two-stage flow shop problems with secondary criterion. Computers & Operations Research, 29(2) (2002) 123-149.
[20] X. J. Wang, C. Y. Zhang, L. Gao, P. G. Li, A survey and future trend of study on multi-objective scheduling, In 2008 Fourth International Conference on Natural Computation (Vol. 6, pp. 382-391)(2008, October), IEEE.
[21] S. M. Jasim, F. H. Ali, Exact and local search methods for solving travelling salesman problem with practical application, Iraqi Journal of Science, 60(5)(2019 ) 1138-1153. https://doi.org/10.24996/ijs.2019.60.5.22
[22] S. Stoppler, C. Bierwirth, The application of a parallel genetic algorithm to the n/m/P/C max flow shop problem, In New Directions for Operations Research in Manufacturing (pp. 161-175) (1992), Springer, Berlin, Heidelberg.
 
International Journal of Nonlinear Analysis and Applications
Volume 13, Issue 1
March 2022
Pages 1649-1658
  • Receive Date: 17 April 2021
  • Revise Date: 03 July 2021
  • Accept Date: 10 September 2021