带有退化维护活动和工件可拒绝的非同类机排序问题

作者：高洁; 邹娟; 隋玉康; 张玉忠^*

来源：运筹学学报, 2023, 27(03): 137-149.

DOI：10.15960/j.cnki.issn.1007-6093.2023.03.011

• 排序
• 非同类机
• 退化维护活动
• 近似算法

本文研究了带有退化维护活动和工件可拒绝的非同类机排序问题。每台机器至多执行一次退化维护活动,退化维护活动的维护时长是其开始时刻的线性非减函数。工件或者被加工并支付生产成本,或者被拒绝并支付拒绝成本。目标是确定每台机器上退化维护活动的位置与所有接受工件的加工顺序使所有接受工件的排序指标、生产成本及所有拒绝工件的拒绝惩罚之和达到最小。当排序指标为最大完工时间时,我们给出一个最坏性能比为2的近似算法。当排序指标为总完工时间、机器总负载及完工时间的总绝对偏差时,我们指出这三个问题都是在多项式时间内可解的。

• 单位
  曲阜师范大学