Approximation algorithms for solving multi-objective optimization problems
Abstract
This paper tries to cover the main aspects/properties related to scheduling problems, approximation algorithms, and multi-objective combinatorial optimization. Then, we try to describe the main techniques that can be used to solve such problems. In this paper, the reviews results relate to multi-objective optimization problems, exact and approximation search, with the aim of getting all Pareto optimal solutions for some NP-hard problems.
References
[1]. A. Allahverdi and T. Aldowaisan, (2004). No-wait flowshops with bicriteria of makespan and maximum lateness. European Journal of Operational Research, 152(1):132–147.
[2]. C. He, Y. Lin and J. Yuan, (2009). A DP algorithm for minimizing makespan and total completion time on a series-batching machine. Information processing letters, 109(12), 603-607.
[3]. G. Sapienza, G. Brestovac, R. Grgurina and T. Seceleanu, (2016). On applying multiple criteria decision analysis in embedded systems design. Design automation for embedded systems, 20(3), 211-238.
[4]. D. Sarkar and J. Modak, (2005). Pareto-optimal solutions for multi-objective optimization of fed-batch bioreactors using nondominated sorting genetic algorithm. Chemical Engineering Science, 60(2):481–492.
[5]. C. Silva and E. Biscaia, (2003). Genetic algorithm development for multi-objective optimization of batch free-radical polymerization reactors. Computers & chemical engineering, 27(8):1329–1344.
[6]. V. T’kindt and J. Billaut, (2006). Multicriteria scheduling: theory, models and algorithms. Springer Science & Business Media.
[7]. B. Lin and A. Jeng, (2004). Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs. International Journal of Production Economics, 91(2):121–134.
[8]. P. Brucker, (2007). Scheduling Algorithms. Springer, Berlin.
[9]. M. Pinedo, (2016). Scheduling Theory, Algorithms, and Systems. Springer, New York.
[10]. A. V. Lotov, V. A. Bushenkov and G. K. Kamenev, (2013). Interactive decision maps: Approximation and visualization of Pareto frontier (Vol. 89). Springer Science & Business Media.
[11]. E. Talbi, (2009). Metaheuristics: From Design to Implementation. 2009, volume 74. John Wiley & Sons.
[12]. G. Alhadi, I. Kacem, P. Laroche and I. M. Osman, (2020). Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines. Annals of Operations Research, 285(1), 369-395.
[13]. Y. Huo and H. Zhao, (2013). Bi-criteria Scheduling on Multiple Machines Subject to Machine Availability Constraints. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (pp. 325-338). Springer, Berlin, Heidelberg.
[14]. C. He, H. Lin, Y. Lin and J. Tian, (2013). Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan. Central European Journal of Operations Research, 21(1), 177-186.
[15]. Y. K. Lin, J. W. Fowler and M. E. Pfund, (2013). Multiple-objective heuristics for scheduling unrelated parallel machines. European Journal of Operational Research, 227(2), 239-253.
[16]. X. Li, L. Amodeo, F. Yalaoui and H. Chehade, (2010). A multiobjective optimization approach to solve a parallel machines scheduling problem. Advances in Artificial Intelligence, 2010.
[17]. C. He, H. Lin and Y. Lin, (2015). Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optimization, 16, 70-75.
[18]. Z. Geng and J. Yuan, (2015). Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness. Theoretical Computer Science, 570, 22-29.
[19]. C. He, Y. Lin and J. Yuan, (2007). Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoretical Computer Science, 381(1-3), 234-240.
[20]. E. Angel, E. Bampis and A. Kononov, (2001). A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. In European Symposium on Algorithms (pp. 194-205). Springer, Berlin, Heidelberg.
[21]. V. Th. Paschos, (2018). Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7. RAIRO - Operations Research, 52:305–314.
[22]. P. Kumar, (2008). A Framework for Multi-objective Optimization and Multi-criteria Decision Making for Design of Electrical Drives. Universiteit Delft.
[23]. S. B Amor, K. Zaras, and E. A. Aguayo, (2017). The value of additional information in multicriteria decision making choice problems with information imperfections. Annals of Operations Research, 253(1):61–76.
[24]. S. B Amor and J. M. Martel, (2014). A new distance measure including the weak preference relation: Application to the multiple criteria aggregation procedure for mixed evaluations. European Journal of Operational Research, 237(3):1165–1169.
[25]. G. Alhadi, I. Kacem, P. Laroche, I. M. Osman, (2018). Maximum Lateness Minimization on Two-Parallel Machine with a Non-availability Interval. In 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT) (pp. 757-762). IEEE.
[26]. D. Williamson and D. Shmoys, (2010). The Design of Approximation Algorithms. Cambridge university press, New York.
[27]. P. Schuurman and G. Woeginger, (2011). Lectures on Scheduling. University of Technology,NL-5600 MB Eindhoven, The Netherlands.
[2]. C. He, Y. Lin and J. Yuan, (2009). A DP algorithm for minimizing makespan and total completion time on a series-batching machine. Information processing letters, 109(12), 603-607.
[3]. G. Sapienza, G. Brestovac, R. Grgurina and T. Seceleanu, (2016). On applying multiple criteria decision analysis in embedded systems design. Design automation for embedded systems, 20(3), 211-238.
[4]. D. Sarkar and J. Modak, (2005). Pareto-optimal solutions for multi-objective optimization of fed-batch bioreactors using nondominated sorting genetic algorithm. Chemical Engineering Science, 60(2):481–492.
[5]. C. Silva and E. Biscaia, (2003). Genetic algorithm development for multi-objective optimization of batch free-radical polymerization reactors. Computers & chemical engineering, 27(8):1329–1344.
[6]. V. T’kindt and J. Billaut, (2006). Multicriteria scheduling: theory, models and algorithms. Springer Science & Business Media.
[7]. B. Lin and A. Jeng, (2004). Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs. International Journal of Production Economics, 91(2):121–134.
[8]. P. Brucker, (2007). Scheduling Algorithms. Springer, Berlin.
[9]. M. Pinedo, (2016). Scheduling Theory, Algorithms, and Systems. Springer, New York.
[10]. A. V. Lotov, V. A. Bushenkov and G. K. Kamenev, (2013). Interactive decision maps: Approximation and visualization of Pareto frontier (Vol. 89). Springer Science & Business Media.
[11]. E. Talbi, (2009). Metaheuristics: From Design to Implementation. 2009, volume 74. John Wiley & Sons.
[12]. G. Alhadi, I. Kacem, P. Laroche and I. M. Osman, (2020). Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines. Annals of Operations Research, 285(1), 369-395.
[13]. Y. Huo and H. Zhao, (2013). Bi-criteria Scheduling on Multiple Machines Subject to Machine Availability Constraints. In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (pp. 325-338). Springer, Berlin, Heidelberg.
[14]. C. He, H. Lin, Y. Lin and J. Tian, (2013). Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan. Central European Journal of Operations Research, 21(1), 177-186.
[15]. Y. K. Lin, J. W. Fowler and M. E. Pfund, (2013). Multiple-objective heuristics for scheduling unrelated parallel machines. European Journal of Operational Research, 227(2), 239-253.
[16]. X. Li, L. Amodeo, F. Yalaoui and H. Chehade, (2010). A multiobjective optimization approach to solve a parallel machines scheduling problem. Advances in Artificial Intelligence, 2010.
[17]. C. He, H. Lin and Y. Lin, (2015). Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optimization, 16, 70-75.
[18]. Z. Geng and J. Yuan, (2015). Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness. Theoretical Computer Science, 570, 22-29.
[19]. C. He, Y. Lin and J. Yuan, (2007). Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoretical Computer Science, 381(1-3), 234-240.
[20]. E. Angel, E. Bampis and A. Kononov, (2001). A FPTAS for approximating the unrelated parallel machines scheduling problem with costs. In European Symposium on Algorithms (pp. 194-205). Springer, Berlin, Heidelberg.
[21]. V. Th. Paschos, (2018). Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7. RAIRO - Operations Research, 52:305–314.
[22]. P. Kumar, (2008). A Framework for Multi-objective Optimization and Multi-criteria Decision Making for Design of Electrical Drives. Universiteit Delft.
[23]. S. B Amor, K. Zaras, and E. A. Aguayo, (2017). The value of additional information in multicriteria decision making choice problems with information imperfections. Annals of Operations Research, 253(1):61–76.
[24]. S. B Amor and J. M. Martel, (2014). A new distance measure including the weak preference relation: Application to the multiple criteria aggregation procedure for mixed evaluations. European Journal of Operational Research, 237(3):1165–1169.
[25]. G. Alhadi, I. Kacem, P. Laroche, I. M. Osman, (2018). Maximum Lateness Minimization on Two-Parallel Machine with a Non-availability Interval. In 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT) (pp. 757-762). IEEE.
[26]. D. Williamson and D. Shmoys, (2010). The Design of Approximation Algorithms. Cambridge university press, New York.
[27]. P. Schuurman and G. Woeginger, (2011). Lectures on Scheduling. University of Technology,NL-5600 MB Eindhoven, The Netherlands.
Published
2022-10-17
How to Cite
BABIKIR, Gais Alhadi.
Approximation algorithms for solving multi-objective optimization problems.
Gezira Journal of Engineering and Applied Sciences, [S.l.], v. 15, n. 2, p. 32-35, oct. 2022.
ISSN 1858-5698. Available at: <http://37.60.236.48/index.php/gjeas/article/view/2151>. Date accessed: 03 june 2026.
Issue
Section
Articles
