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

doi:10.15960/j.cnki.issn.1007-6093.2025.04.002

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

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

李大伟¹^,*(), 李刚刚²

1. 上海立信会计金融学院统计与数学学院, 上海 201620
2. 江西财经大学信息管理学院, 江西南昌 330013

收稿日期:2022-11-01 出版日期:2025-12-15 发布日期:2025-12-11
通讯作者: 李大伟 E-mail:dwli@lixin.edu.cn
基金资助:
国家自然科学基金(11901255)

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

Dawei LI¹^,*(), Ganggang LI²

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 Online:2025-12-15 Published:2025-12-11
Contact: Dawei LI E-mail:dwli@lixin.edu.cn

摘要/Abstract

摘要：

本文主要研究人员不可用及工件带退化效应的单机排序问题, 目标是极小化工件的加权总完工时间。与机器有不可用时间限制的排序问题不同, 工件可以在人员不可用的时间段内加工, 但是不能在这个时间段内开工也不能在这个时间段内完工。我们首先证明当存在两个人员不可用的时间段时, 这个问题不存在最坏情形性能比为常数的多项式时间近似算法, 除非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

中图分类号:

O221.7

李大伟, 李刚刚. 考虑人员不可用及工件带退化效应的单机排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 14-26.

Dawei LI, Ganggang LI. Single-machine scheduling with operator non-availability periods and deteriorating jobs[J]. Operations Research Transactions, 2025, 29(4): 14-26.

参考文献 19

1	Brauner N, Lehoux-Lebacque V, Celse B, et al. Planification d'expériences dans l'industrie chimique[C]//Colloque de l'Institut de la Production et des organisations Industrielles, 2007: 21-32.
2	BraunerN,FinkeG,Lehoux-LebacqueV,et al.Operator non-availability periods[J].4OR-A Quarterly Journal of Operations Research,2009,7(3):239-253. doi: 10.1007/s10288-008-0084-6
3	RapineC,BraunerN,FinkeG,et al.Single machine scheduling with small operator-nonavailability periods[J].Journal of Scheduling,2012,15(2):127-139. doi: 10.1007/s10951-012-0269-x
4	ChenY,ZhangA,TanZ Y.Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time[J].Information Sciences,2013,251,150-163. doi: 10.1016/j.ins.2013.07.003
5	KacemI,KellererH,SeifaddiniM.Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval[J].Journal of Combinatorial Optimization,2016,32(3):970-981. doi: 10.1007/s10878-015-9924-4
6	WanL,YuanJ J.Single-machine scheduling with operator non-availability to minimize total weighted completion time[J].Information Sciences,2018,445-446,1-5. doi: 10.1016/j.ins.2018.03.005
7	ZuoL L,SunZ X,LuL F,et al.Single-machine scheduling with rejection and an operator non-availability interval[J].Mathematics,2019,7(8):668. doi: 10.3390/math7080668
8	LiD W,LuX W.Two-machine flow shop scheduling with an operator non-availability period to minimize makespan[J].Journal of Combinatorial Optimization,2020,39(4):1060-1078. doi: 10.1007/s10878-020-00548-6
9	GuptaJ N D,GuptaS K.Single facility scheduling with nonlinear processing times[J].Computers & Industrial Engineering,1988,14(4):387-393.
10	BrowneS,YechialiU.Scheduling deteriorating jobs on a single processor[J].Operations Research,1990,38(3):495-498. doi: 10.1287/opre.38.3.495
11	ChengT C E,DingQ,LinB M T.A concise survey of scheduling with time-dependent processing times[J].European Journal of Operational Research,2004,152(1):1-13. doi: 10.1016/S0377-2217(02)00909-8
12	GawiejnowiczS.Time-Dependent Scheduling[M].Berlin:Springer,2008.
13	SunX,GengX N.Single-machine scheduling with deteriorating effects and machine maintenance[J].International Journal of Production Research,2019,57(10):3186-3199. doi: 10.1080/00207543.2019.1566675
14	LiS S,FanB Q.Single-machine scheduling with proportionally deteriorating jobs subject to availability constraints[J].Asia-Pacific Journal of Operational Research,2012,29(4):1250019. doi: 10.1142/S0217595912500194
15	GawiejnowiczS.A review of four decades of time-dependent scheduling: Main results, new topics, and open problems[J].Journal of Scheduling,2020,23(1):3-47. doi: 10.1007/s10951-019-00630-w
16	MosheiovG.Scheduling jobs under simple linear deterioration[J].Computers & Operations Research,1994,21(6):653-659.
17	NgC T,BarketauM S,ChengT C E,et al."Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation[J].European Journal of Operational Research,2010,207(2):601-604. doi: 10.1016/j.ejor.2010.05.034
18	WegenerI.Complexity Theory: Exploring the Limits of Efficient Algorithms[M].Berlin:Springer,2005.
19	SahniS K.Algorithms for scheduling independent tasks[J].Journal of the ACM,1976,23(1):116-127. doi: 10.1145/321921.321934

[1]	赵娣, 余金, 鲁习文. 单机两代理串行分批排序问题的近似算法[J]. 运筹学学报（中英文）, 2025, 29(2): 184-193.
[2]	崔同欣, 夏倩, 张新功. 基于松弛工期的总加权误工单机双代理排序问题[J]. 运筹学学报（中英文）, 2025, 29(1): 31-40.
[3]	杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.
[4]	李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报（中英文）, 2024, 28(4): 18-28.
[5]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[6]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[7]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[8]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[9]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.
[10]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[11]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[12]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[13]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[14]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[15]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价