China
Africa
Explore chapters and articles related to this topic
Models and Algorithms for Machine Scheduling with Setup Times
Published in Cornelius Leondes, Computer-Aided Design, Engineering, and Manufacturing, 2019
The practical usefulness of the theory of NP-completeness is that, once a problem is shown to be NP-complete, approaches to solving the problem are restricted to (1) finding exponential time algorithms that are guaranteed to solve the problem optimally, or (2) accepting that finding optimal solutions for problems of practical size may not be possible in reasonable time, and developing algorithms which merely perform well.
Disassembly Line Balancing
Published in Surendra M. Gupta, A. J. D. (Fred) Lambert, Environment Conscious Manufacturing, 2007
Seamus M. McGovern, Surendra M. Gupta
NP-completeness provides strong evidence that the problem cannot be solved with a polynomial time algorithm (the theory of NP-completeness is applied only to decision problems). Many problems that are polynomial solvable differ only slightly from other problems that are NP-complete. While 3-satisfiability and 3-dimensional matching are NP-complete, the related 2-satisfiability and 2-dimensional matching problems can be solved in polynomial time (polynomial time algorithm design is detailed in Refs. 1 and 46). If a problem is NP-complete, some subproblem (created by additional restrictions being placed on the allowed instances) may be solvable in polynomial time. Certain encoding schemes and mathematical techniques can be used on some size-limited cases of NP-complete problems (an example is a dynamic programming approach to partition that results in a search space size equal to the size of the instance multiplied by the log of the sum of each number in the instance) enabling the solution by what is known as a “pseudopolynomial time algorithm.” In the PARTITION case, this results in a polynomial time solution as long as extremely large input numbers are not found in the instance. Problems for which no pseudopolynomial time algorithm exists (assuming P ≠ NP) are known as “NP-complete in the strong sense” (also, unary NP-complete—referring to allowance for a nonconcise or unary encoding scheme notation where a string of n 1s represents the number n—with an alternative being binary NP-complete). Typical limiting factors for NP-complete problems to have a pseudopolynomial time algorithm include the requirement that the problem be a number problem (versus a graph problem, logic problem, etc.) and be size constrained, typically in the number of instance elements (n in DLBP) and the size of the instance elements (PRTk in DLBP). Formally, an algorithm that solves a problem L will be called a pseudopolynomial time algorithm for L if its time complexity function is bound above as a function of the instance I by a polynomial function of the two variables: Length[I] and Max[I]. A general NP-completeness result implies that the problem cannot be solved in polynomial time in all the chosen parameters.
A capacity matching model in a collaborative urban public transport system: integrating passenger and freight transportation
Published in International Journal of Production Research, 2022
Feng Li, Xin Guo, Li Zhou, Jianjun Wu, Tongfei Li
For a small test network, the CPLEX could obtain good solutions. However, the model belongs to NP-completeness. We need to explore more efficient heuristic algorithms to solve this problem, because CPLEX would obtain solutions at the expense of the CPU time or even fail to solve for a larger network. In this section, the results of IABC are compared with the original ABC and CPLEX methods. Calculation results are illustrated in Figures 8–9. We obtain the optimal total synchronisation times for all packages (6760s), the same as applying the CPLEX Solver. We conclude that all algorithms attach optimal objective function values. However, the CPU times are different. It takes IABC 337s with 2000 iterations and captures the optimal solution in the 169-th iteration. While ABC takes 337s with 2000 iterations, and results converge to the global minimum value in the 1594-th iteration. Results demonstrate that the IABC has high efficiency.
Combining evolutionary computation with the variable neighbourhood search in creating an artificial music composer
Published in Connection Science, 2019
The rest of the paper is as follows. Section 2 discusses the related work in seven different subsections, namely (i) the relationship between mathematics and music, (ii) music and NP-completeness, (iii) pattern extraction in music, (iv) quantifying listeners’ expectation with using the concept of entropy, (v) music composition with Markov chains, (vi) music composition with variable neighbourhood search, and (vii) music composition with genetic algorithms. Section 3 describes the SYMPHONY by presenting its constructing components consisting of (i) the music-rules-handling module, (ii) the pitch, rhythm as well as chord generation modules, and (iii) the modules for timber and dynamics modification. Section 4 describes the examples generated by the SYMPHONY, and novel points regarding their generation. Section 5 presents concluding remarks and future research directions.
Approximation Scheme for Order Acceptance and Scheduling on a Single Machine with a Reserved Job
Published in American Journal of Mathematical and Management Sciences, 2019
Mengjie Wu, Hao Tian, Wenchang Luo
The remainder of the article is organized as follows. In Section 2, a dynamic programming exact algorithm running in pseudo-polynomial time is derived. In Section 3, by using the sparsing technique, one can choose a series of discrete intervals with well-structured properties to approximate a continuous interval; given an arbitrary small positive number , the derived dynamic programming is transformed into an FPTAS, which achieves a performance ratio of . Finally, we summarize our work and claim that given the NP-hardness, our result is the best possible from an approximation algorithm perspective by the NP-completeness theory (Garey & Johnson, 1979).