in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MC...in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.展开更多
The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the mach...The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.展开更多
We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the long...We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.展开更多
文摘in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.
基金Supported by the National Natural Science Foundation of China(11871213,71431004).
文摘The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.
文摘We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.
