工件可拒绝平行机排序

The Scheduling on Parallel Batch with Job-rejection

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.

It is considered the scheduling on m unbounded parallel batch matchines with release dates and rejections of jobs.A job is either rejected with a certain penalty having to be paid,or accepted and processed in batches on one of the m machines.The processing time of a batch is defined as the longest processing time of the jobs contained in it.The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs.When m is a fixed number,a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme are provided for the problem.