English

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (1): 179-187.doi: 10.15960/j.cnki.issn.1007-6093.2026.01.012

• • 上一篇    

在NDP约束条件下考虑带退化效应的单机在线调度

孟兰梦1, 马冉1,†, 张玉忠2   

  1. 1. 青岛理工大学管理工程学院, 山东青岛 266525;
    2. 曲阜师范大学运筹学研究院, 山东日照 276826
  • 收稿日期:2022-12-20 发布日期:2026-03-16
  • 通讯作者: 马冉 E-mail:sungirlmr@126.com
  • 基金资助:
    国家自然科学基金 (Nos. 12271295, 12371319), 山东省自然科学基金 (Nos. ZR2020MA028, ZR2024MA026, ZR2025MS102)

Single-machine online scheduling with NDP constraint and deterioration

MENG Lanmeng1, MA Ran1,†, ZHANG Yuzhong2   

  1. 1. School of Management Engineering, Qingdao University of Technology, Qingdao 266525, Shandong, China;
    2. Institute of Operations Research, Qufu Normal University, Rizhao 276826, Shandong, China
  • Received:2022-12-20 Published:2026-03-16

PDF

2

摘要： 本文研究工件处理在无延迟加工(NDP) 约束条件下具有退化效应的在线生产调度问题。工件是以时间在线的方式到达, 同时要求被不可中断地加工, 其加工时间的模型是$p_{j}=a+b_{j}t$ ($a>0$), 目标是极小化最大加权完工时间。针对此问题, 首先利用对手法证明出下界为$1+b_{\max}$, 然后设计出一个竞争比为$2+b_{\max}$ 的在线算法, 最后对于该模型进行数据模拟以验证在线算法的有效性和正确性。

关键词: NDP约束, 退化效应, 单机, 在线调度, 最大加权完工时间

Abstract: This paper studies the single machine online production scheduling with non-delayed processing (NDP) constraint as well as deterioration. Jobs arriving over time on-line are processed non-preemptive on machine. The model of job processing time is $p_{j}=a+b_{j}t (a>0$). Its objective is to minimize the maximum weighted completion time. Firstly, we derive the lower bound of the considered problem is $1+b_{\max}$ by means of adversary method. Then we design a online algorithm with the competitive ratio of $2+b_{\max}$. Moreover, these online models are simulated to verify the effectiveness and correctness of online algorithm.

Key words: NDP constraint, deterioration, single machine, online scheduling, maximum weighted completion time

中图分类号: