Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (1): 165-175.doi: 10.1007/s40305-018-0207-5

• • 上一篇    下一篇

  

  • 收稿日期:2017-08-30 修回日期:2017-12-16 出版日期:2020-03-30 发布日期:2020-02-18
  • 通讯作者: Wen-Chang Luo E-mail:luowenchang@163.com
  • 基金资助:
    The research was supported by the Natural Science Foundation of Ningbo (No. 2016A610078) and the K.C. Wong Magna Fund in Ningbo University.

On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs

Wen-Chang Luo   

  1. Faculty of Science, Ningbo University, Ningbo 315211, Zhejiang, China
  • Received:2017-08-30 Revised:2017-12-16 Online:2020-03-30 Published:2020-02-18
  • Contact: Wen-Chang Luo E-mail:luowenchang@163.com

Abstract: We investigate a single-machine scheduling problem, where a deteriorating rate-modifying activity can be performed on the machine to reduce the processing times of jobs.The objective is to minimize the number of tardy jobs.Under the assumption that the duration of the rate-modifying activity is a nonnegative and nondecreasing functionon its starting time,we propose an optimal polynomial time algorithm running in O(n3) time.

Key words: Scheduling, Rate-modifying activity, Due date, Polynomial time algorithm

中图分类号: