We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due date.By preprocessing and...We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due date.By preprocessing and constructing an auxiliary instance which has several good properties,for any desired accuracy,we propose an efficient polynomial time approximation scheme with running time O(f(1/ε)n),where n is the number of jobs and f(1/ε)is exponential in 1/ε,and a fully polynomial time approximation scheme with running time O(1/ε^(2m+1)+n)when the number of machines is fixed.展开更多
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.展开更多
We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of a...We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of all jobs and the total load on all machines.We show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all machines.We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time.The objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.展开更多
In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actu...In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date.The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs.For the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary sense.Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm.Furthermore,we propose a fully polynomial time approximation scheme.For the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.展开更多
基金the National Natural Science Foundation of China(No.12071417)the Project for Innovation Team(Cultivation)of Yunnan Province.
文摘We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due date.By preprocessing and constructing an auxiliary instance which has several good properties,for any desired accuracy,we propose an efficient polynomial time approximation scheme with running time O(f(1/ε)n),where n is the number of jobs and f(1/ε)is exponential in 1/ε,and a fully polynomial time approximation scheme with running time O(1/ε^(2m+1)+n)when the number of machines is fixed.
文摘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.
基金This work was supported by the National Natural Science Foundation of China(Nos.11071142,11201259)the Natural Science Foundation of Shan Dong Province(No.ZR2010AM034)+1 种基金the Doctoral Fund of the Ministry of Education(No.20123705120001)We thank the two anonymous reviewers for their helpful and detailed comments on an earlier version of our paper.
文摘We consider several uniform parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time.The objectives are to minimize the total completion time of all jobs and the total load on all machines.We show that the problems are polynomially solvable when the increasing rates are identical for all jobs;we propose a fully polynomial-time approximation scheme for the standard linear deteriorating function,where the objective function is to minimize the total load on all machines.We also consider the problem in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time.The objective is to find a schedule which minimizes the time by which all jobs are delivered,and we propose a fully polynomial-time approximation scheme to solve this problem.
基金supported by the National Natural Science Foundation of China(Nos.12271295 and 12001313)the Provincial Natural Science Foundation of Shandong(No.ZR2022MA019).
文摘In this paper,we consider the single-machine scheduling with step-deteriorating jobs and rejection.Each job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating date.The objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs.For the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary sense.Then we present two pseudo-polynomial algorithms and a 2-approximation algorithm.Furthermore,we propose a fully polynomial time approximation scheme.For the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.
