China
Africa
Explore chapters and articles related to this topic
Use of Metaheuristics in Reverse Logistics and De-manufacturing
Published in Eren Özceylan, Surendra M. Gupta, Sustainable Production and Logistics, 2021
Seamus M. McGovern, Surendra M. Gupta
Cook provided the foundations for NP-completeness in 1971 by showing that a polynomial-time reduction from one problem to another ensures any polynomial-time algorithm used on one can be used to solve the other. In addition, Cook emphasized the class of NP-decision problems that can be solved on a nondeterministic computer (a fictitious computer that operates in a manner that is not predictable; that is, a computer that guesses solutions). The final significant contribution of that paper was the proof that every problem in NP can be reduced to one particular problem in NP (the satisfiability problem or SAT) and the suggestion that other problems in NP may share the SAT’s property of being the hardest problem in NP. This group of the hardest problems in NP is the class of NP-complete problems.
Optimal allocation of public parking spots in a smart city: problem characterisation and first algorithms
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2019
Javier Arellano-Verdejo, Federico Alonso-Pecina, Enrique Alba, Adolfo Guzmán Arenas
● constructing a polynomial time reduction from to . Theorem 1. The optimal allocation of public parking spots is NP-complete.Proof: A decision problem is a question in a formal system with a yes-or-no answer, depending on the values of some input parameters, and this is NP if the instances where the answer is ‘yes’ have efficiently verifiable proofs. More precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time. For the problem presented in this paper, the solution can be verified using the method shown in Equation (12). The temporal complexity of Equation (12) grows linearly with respect to the size of the permutation that is , so it is clear that the problem is NP.
A new split-based hybrid metaheuristic for the reconfigurable transfer line balancing problem
Published in International Journal of Production Research, 2021
Y. Lahrichi, N. Grangeon, L. Deroussi, S. Norre
We show that the TSP (Travelling Salesman Decision Problem) is reduced to the considered problem. Indeed, the TSP is the task of deciding whether there exists a ‘tour’ visiting a given set of cities and returning to the initial city such that the total distance travelled is less or equal to a constant B. Then, an instance of the TSP could be mapped with an instance of the RTLB problem where operations represent cities, the setup times between operations represent distances between cities and such that and C = B. This is a polynomial time reduction which justifies the NP-Hardness of our problem.