In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' ...In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.展开更多
Two sets are close if their symmetric difference is a sparse set. It is shown that NP-hard sets are not C=P-close unless NP C=C=P. This improves the previous result and has implication in quantum compulation.
Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible s...Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.展开更多
The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is h...The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.展开更多
文摘In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.
文摘Two sets are close if their symmetric difference is a sparse set. It is shown that NP-hard sets are not C=P-close unless NP C=C=P. This improves the previous result and has implication in quantum compulation.
基金Research is supported by the National 863 Program ( No.863- 306- Z T
文摘Assume there are several states, and the objective function f\+s(x) is linked with each state s. Robust optimization is to solve the following problem: min x∈X max s∈Sf\+s(x)where X is the feasible solution set, and S is the collection of states.\;It has been showed that most of robust combinatorial optimization problems are NP\|hard in strong sense. In this paper, we will discuss the borderline between the ′easy′ and the ′hard′ cases of robust combinatorial optimization problems, and further present a heuristic frame work to solve the ′hard′ problems and discuss their concrete implementation of the heuristic method.
基金the Deanship of Scientific Research,Imam Mohammad Ibn Saud Islamic University(IMSIU),Saudi Arabia,for funding this research work through Grant No.(221412020).
文摘The generalized travelling salesman problem(GTSP),a generalization of the well-known travelling salesman problem(TSP),is considered for our study.Since the GTSP is NP-hard and very complex,finding exact solutions is highly expensive,we will develop genetic algorithms(GAs)to obtain heuristic solutions to the problem.In GAs,as the crossover is a very important process,the crossovermethods proposed for the traditional TSP could be adapted for the GTSP.The sequential constructive crossover(SCX)and three other operators are adapted to use in GAs to solve the GTSP.The effectiveness of GA using SCX is verified on some GTSP Library(GTSPLIB)instances first and then compared against GAs using the other crossover methods.The computational results show the success of the GA using SCX for this problem.Our proposed GA using SCX,and swap mutation could find average solutions whose average percentage of excesses fromthe best-known solutions is between 0.00 and 14.07 for our investigated instances.
