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.展开更多
基金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.
