An ND two-agent scheduling problem with rejection on a single machine related to the total completion time and makespan

Expand
  • 1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, Henan, China
    2. College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, Henan, China

Received date: 2021-09-08

  Online published: 2024-12-20

Copyright

, 2024, All rights reserved, without authorization

Abstract

In this paper, we consider the ND two-agent scheduling problem with rejection on a single machine. In this problem, there are two agents $A $ and $B $ and the job sets of them are denoted by $\mathcal{J}^A $ and $\mathcal{J}^B$ respectively. In the classical CO two-agent scheduling, two agents are competitive, i.e., $\mathcal{J}^A\cap \mathcal{J}^B=\varnothing $. However, in the ND two-agent scheduling, two agents may have common jobs, i.e., $\mathcal{J}^A\cap \mathcal{J}^B\neq\varnothing $ is allowed. In scheduling problems with rejection, each job is either accepted and processed on the machine, or rejected by paying a corresponding rejection cost. In this paper, we study the ND two-agent scheduling with rejection. In particular, we consider a constrained scheduling problem. That is, the objective is to minimize the sum of the total completion time $\sum C_j^A $ of accepted $A $-jobs and the total rejection cost of rejected $A $-jobs subject to an upper bound $Q $ on the sum of the makespan $C_{\max}^B $ of accepted $B $-jobs and the total rejection cost of the rejected $B $-jobs. For this problem, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme.

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.04.006

References

1 BartalY,LeonardiS,SpaccamelaA M,et al.Multiprocessor scheduling with rejection[J].SIAM Journal on Discrete Mathematics,2000,13,64-78.
2 HoogeveenH,SkutellaM,WoegingerG J.Preemptive scheduling with rejection[J].Mathematics Programming,2003,94(2):361-374.
3 EngelsD W,KargerD R,KolliopoulosS G,et al.Techniques for scheduling with rejection[J].Journal of Algorithms,2003,49,175-191.
4 ShabtayD,GasparN,KaspiM.A survey on offline scheduling with rejection[J].Journal of Scheduling,2013,16(1):3-28.
5 张玉忠.工件可拒绝排序问题综述[J].运筹学学报,2020,24(2):111-130.
6 BakerR,SmithJ.A multiple criterion model for machine sheduling[J].Journal of Scheduling,2003,6(1):7-16.
7 AgnetisA,MirchandaniP,PacciarelliD,et al.Scheduling problems with two competing agents[J].Operations Research,2004,52(2):229-242.
8 ChengT C E,NgC T,YuanJ J.Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs[J].Theoretical Computer Science,2008,188(2):603-609.
9 AgnetisA,BillautJ,GawiejnowiczS,et al.Multiagent Scheduling$:$ Models and Algorithms[M].Berlin:Springer,2014.
10 FengQ,FanB Q,LiS S,et al.Two-agent scheduling with rejection on a single machine[J].Applied Mathematics Modelling,2015,39(3/4):1183-1193.
11 MorB,MosheiovG.Minimizing maximum cost on a single machine with two competing agents and job rejection[J].Journal of the Operational Research Society,2016,67,1524-1531.
12 LiD W,LuX W.Two-agent parallel-machine shceduling with rejection[J].Theoretical Computer Science,2017,703,66-75.
13 OronD.Two-agent sheduling problems under rejection budget constraints[J].Omega,2021,102,102313.
14 GrahamR L,LawerE L,LenstraJ K,et al.Optimization and approximation in deterministric sequencing and scheduling: a survey[J].Annals of Discrete Mathematics,1979,5,287-376.
Outlines

/