中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 4: 14 - 26

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.04.002

Research Article

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

  • Dawei LI ,
  • Ganggang LI
Expand
  • 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 date: 2022-11-01

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

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

Cite this article

Dawei LI , Ganggang LI . Single-machine scheduling with operator non-availability periods and deteriorating jobs[J]. Operations Research Transactions, 2025 , 29(4) : 14 -26 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.002

References

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.
3 RapineC,BraunerN,FinkeG,et al.Single machine scheduling with small operator-nonavailability periods[J].Journal of Scheduling,2012,15(2):127-139.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Options
Outlines

/

〈 〉