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

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

Abstract

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

CLC Number:

O221.7

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

References 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]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[2]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.
[3]	Guohua WAN, Shan WANG, Tengfang HUANG. Appointment scheduling in service systems: A survey and extension [J]. Operations Research Transactions, 2025, 29(3): 61-76.
[4]	Wei LU, Xingyu LU, Ding ZOU, Boxiao CHEN, Yihan ZHOU, Guochuan ZHANG. Research on computing power scheduling problem and technology in green computing [J]. Operations Research Transactions, 2025, 29(3): 179-201.
[5]	Siqi GUO, Ping ZHOU, Yiwei JIANG, Min JI. Single-machine scheduling with carbon emission cost and piece-rate maintenance [J]. Operations Research Transactions, 2025, 29(2): 68-79.
[6]	Di ZHAO, Jin YU, Xiwen LU. Approximation algorithms for two-agent serial batching scheduling problems [J]. Operations Research Transactions, 2025, 29(2): 184-193.
[7]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[8]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[9]	Tongxin CUI, Qian XIA, Xingong ZHANG. Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness [J]. Operations Research Transactions, 2025, 29(1): 31-40.
[10]	Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities [J]. Operations Research Transactions, 2025, 29(1): 142-158.
[11]	Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times [J]. Operations Research Transactions, 2024, 28(4): 18-28.
[12]	Bo XU, Weimin MA, Hua KE, Hao ZHANG. Research on the multi-objective model and algorithm for aircraft takeoff/landing scheduling based on rank 2 matrix approximation [J]. Operations Research Transactions, 2024, 28(4): 29-43.
[13]	Qing GE, Lingfa LU, Jinjiang YUAN, Liqi ZHANG. An ND two-agent scheduling problem with rejection on a single machine related to the total completion time and makespan [J]. Operations Research Transactions, 2024, 28(4): 66-74.
[14]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[15]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 19

Related Articles 15

Recommended Articles

Metrics

Comments