运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 137-149.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.011

•   • 上一篇    下一篇

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

高洁1, 邹娟1, 隋玉康1, 张玉忠2,*()   

  1. 1. 曲阜师范大学数学科学学院, 山东曲阜 273165
    2. 曲阜师范大学运筹学研究院, 山东日照 276826
  • 收稿日期:2022-01-18 出版日期:2023-09-15 发布日期:2023-09-14
  • 通讯作者: 张玉忠 E-mail:yuzhongrz@163.com
  • 作者简介:张玉忠, E-mail: yuzhongrz@163.com
  • 基金资助:
    国家自然科学基金(12271295)

Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection

Jie GAO1, Juan ZOU1, Yukang SUI1, Yuzhong ZHANG2,*()   

  1. 1. School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China
    2. Institute of Operation Research, Qufu Normal University, Rizhao 276826, Shandong, China
  • Received:2022-01-18 Online:2023-09-15 Published:2023-09-14
  • Contact: Yuzhong ZHANG E-mail:yuzhongrz@163.com

摘要:

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

关键词: 排序, 非同类机, 退化维护活动, 近似算法

Abstract:

We study unrelated parallel-machine scheduling problems with deteriorating maintenance activities and job rejection. Each machine has at most one deteriorating maintenance activity throughout the scheduling horizon. The duration of the maintenance activity increases linearly with its starting time. Each job is either processed and it incurs a production cost, or is rejected with a penalty cost. The objective is to find the position of the maintenance activity of each machine and the sequence of the accepted jobs such that the scheduling cost of all accepted jobs plus the total cost of rejecting and processing jobs is minimized. When the scheduling cost is the makespan, we provide an approximation algorithm with worst-case ratio of 2. When the scheduling costs are the total completion time, the total machine load and the total absolute deviation of completion times, we show that the three versions of the scheduling problem can be optimally solved in polynomial time.

Key words: scheduling, unrelated machine, deteriorating maintenance activity, approximation algorithm

中图分类号: