English

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 14-26.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.002

• • 上一篇    

考虑人员不可用及工件带退化效应的单机排序问题

李大伟1,†, 李刚刚2   

  1. 1. 上海立信会计金融学院统计与数学学院, 上海 201620;
    2. 江西财经大学信息管理学院, 江西南昌 330013
  • 收稿日期:2022-11-01 发布日期:2025-12-11
  • 通讯作者: 李大伟 E-mail:dwli@lixin.edu.cn
  • 基金资助:
    国家自然科学基金(No.11901255)

Single-machine scheduling with operator non-availability periods and deteriorating jobs

LI Dawei1,†, LI Ganggang2   

  1. 1 School of Statistics and Mathematics, Shanghai Lixin University of Accounting and Finance, Shanghai 201620, China;
    2. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, Jiangxi, China
  • Received:2022-11-01 Published:2025-12-11

PDF

4

摘要： 本文主要研究人员不可用及工件带退化效应的单机排序问题, 目标是极小化工件的加权总完工时间。与机器有不可用时间限制的排序问题不同, 工件可以在人员不可用的时间段内加工, 但是不能在这个时间段内开工也不能在这个时间段内完工。我们首先证明当存在两个人员不可用的时间段时, 这个问题不存在最坏情形性能比为常数的多项式时间近似算法, 除非P=NP。当只存在一个人员不可用的时间段时, 我们给出一个伪多项式时间算法和一个完全多项式时间近似方案(FPTAS)。

关键词: 排序, 人员不可用, 退化工件, 加权总完工时间, 完全多项式时间近似方案

Abstract: The scheduling problem with operator non-availability periods and deteriorating jobs on a single machine is studied in this paper. The objective is to minimize the total weighted completion time. Unlike scheduling with machine non-availability constraints, a job can be processed in the operator non-availability time interval but can neither start nor complete in this period. We first show that there exists no polynomial-time approximation algorithm with a constant worst-case bound when the problem has two operator non-availability periods unless P=NP. We then present a pseudo-polynomial time algorithm and a fully polynomial-time approximation scheme (FPTAS) when there exists only one operator non-availability period.

Key words: scheduling, operator non-availability, deteriorating jobs, total weighted completion time, fully polynomial-time approximation scheme

中图分类号: