带有退化、拒绝和不可用区间的单机排序问题

Deteriorating Jobs Scheduling on a Single Machine with Rejection and a Fixed Non-Availability Interval

【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间a_(j)的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。

[Purposes]Single machine scheduling with deteriorating jobs,rejection and availability constraints are considered.[Methods]It is assumed that jobs have a different basic processing time and same deterioration rate,jobs can be rejected by paying penalties,the machines may be unavailable in a specified time intervals and jobs are non-resumable.The objective is to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected job.[Results]For the NP-hard problem,the optimal solution can be obtained by sequencing in non-decreasing order of a_(j) of the jobs before and after the unavailable interval.A pseudo-polynomial-time dynamic programming and a fully polynomial-time approximation scheme are designed.[Conclusions]The existing models are generalized.