China
Africa
Explore chapters and articles related to this topic
EO for Production Planning and Scheduling
Published in Yong-Zai Lu, Yu-Wang Chen, Min-Rong Chen, Peng Chen, Guo-Qiang Zeng, Extremal Optimization, 2018
Yong-Zai Lu, Yu-Wang Chen, Min-Rong Chen, Peng Chen, Guo-Qiang Chen
To make a manufacturing enterprise more competitive and profitable in the global marketplace, the profit-driven “make-to-order” or “make-to-stock” business model has been applied widely in manufacturing management. Among multidimensional business and production decisions, computer-aided production planning and scheduling to optimize desired business objectives subject to multiple sophisticated constraints has been one of the most important decisions. In general, many production-scheduling problems can be formulated as constrained combinatorial optimization models that are usually NP-hard problems, particularly for those large-scale real-world applications. This kind of scheduling problem is generally difficult to be solved with traditional optimization techniques. Consequently, many approximation methods, for example, metaheuristics, have been the major approaches to such kind of constrained COP. Although approximation algorithms do not guarantee achieving optimal solutions, they can attain near-optimal solutions with reasonable computation time.
Approximation algorithms for clustering
Published in Pratyay Kuila, Prasanta K. Jana, Clustering and Routing Algorithms for Wireless Sensor Networks, 2017
Pratyay Kuila, Prasanta K. Jana
There are many optimization problems that are NP-complete or NP-hard in nature and as such there is a polynomial time solution for them. However, for such problems, we do not require an exact/optimal solution for many practical applications. Approximation algorithms are some alternative approaches that provide approximate or near optimal solutions in polynomial time. Approximation algorithms are used for many optimization problems where exact polynomial-time algorithms are known but are too expensive due to the input size [128]. Some popular examples of such problems for which approximation algorithms have been developed include vertex cover, set cover, jon scheduling, bin-packing, and travelling salesperson problems. Ideally, the solution may go optimal up to a small constant factor, say within 5% of the optimal solution. The ratio between the result obtained by an approximation algorithm and the optimal result is called the approximation ratio of the algorithm. An algorithm with approximation ratio k is called a k-approximation algorithm. For example, an approximation algorithm that results a solution of cost 2 in solving a given problem that has an optimal cost 1 has approximation ratio 2. Therefore, the algorithm will be called a 2-approximation algorithm. Clearly, the approximation ratio of an algorithm is greater than or equal to 1 and it is exactly equal to 1 if and only if it has got an optimal solution. Approximation algorithms attract huge attention for being used in many applications of wireless sensor networks, computational biology, transportation planning, and inventory management.
Simulated-annealing-based hyper-heuristic for flexible job-shop scheduling
Published in Engineering Optimization, 2022
Kelvin Ching Wei Lim, Li-Pei Wong, Jeng Feng Chin
Approximation algorithms do not guarantee optimality, especially for large and complex FJSP instances. These algorithms can return sub-optimal solutions within a short period of time. This is particularly useful when computational resources are limited. Heuristics, metaheuristics and hyper-heuristics are examples of approximation algorithms. Heuristics such as the dispatching rule represent a quick and straightforward optimization technique. However, their performance depends heavily on problem characteristics (Zhou and Yang 2019). Metaheuristics such as the artificial bee colony algorithm (Ferreira et al.2020) and differential evolution (Cao, Shi, and Chang 2022) are search algorithms that iteratively explore and exploit the solution space for a solution. Nonetheless, parameter tuning for a metaheuristic can be time-consuming and limits its reusability (Qu et al.2015).
Research on reducing fuzzy test sample set based on heuristic genetic algorithm
Published in Systems Science & Control Engineering, 2021
Zhihua Wang, Manman Cheng, Yongjian Wang
Approximation algorithms are algorithms used to find approximation methods to solve optimization problems. Approximation algorithms are usually related to NP-hard problems. Since it is impossible to solve the NP-hard problem by an effective polynomial time exact calculation, a polynomial time suboptimal solution is obtained. Unlike heuristic algorithms, only reasonable solutions are usually found fairly quickly, requiring a provable solution quality and a provable run time range, even if the approximation algorithm usually yields a quality-assured solution. The approximation algorithm refers to the scenario or accuracy of using the relevant algorithm to solve some practical problems, and the solution given is the theoretical optimal solution. In the reduction of the sample set, the approximation algorithm refers to giving the smallest sample set of samples as accurately as possible, and obtaining high-quality samples is the only standard of the approximation algorithm (Liu et al., 2020).
Approximation algorithms in partitioning real-time tasks with replications
Published in International Journal of Parallel, Emergent and Distributed Systems, 2018
Jian (Denny) Lin, Albert M. K. Cheng, Gokhan Gercek
Because of the NP-Hardness, it is not possible to solve the partitioning problem within polynomial time for large-sized instances. We target at using approximation algorithms to solve the problem. An approximation algorithm is an algorithm running in polynomial time to approximate the optimal solution within a bounded error. The following definitions are used in the paper.