基于松弛工期的总加权误工单机双代理排序问题

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

Abstract

Abstract:

This paper studies the scheduling problems with two competing agents on a single machine to minimize the total weighted tardiness under slack due date, where the slack due date of the job is equal to its actual processing time plus a certain slack variable. It includes two models: the first model is to minimize the total weighted tardiness of the first agent under the condition that the total number of tardiness jobs of the second agent does not exceed a given value; the second model is to minimize the total weighted tardiness of the first agent that the total completion time of the second agent does not exceed a given value. The optimal properties are given by dynamic programming. The pseudo-polynomial time algorithm and its time complexity is presented. Finally, two experiment examples are given to illustrate the feasibility of the algorithm.

Key words: scheduling, two-agent, total weighted tardiness, dynamical programming algorithm

CLC Number:

O223

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.

Figures/Tables 4

References 14

1	Lawler E L . A/pseudopolynomial0algorithm for sequencing jobs to minimize total tardiness[J]. Annals of Discrete Mathematics, 1977, 1, 331- 342.
2	Potts C N , Van Wassenhove L N . A branch and bound algorithm for the total weighted tardiness problem[J]. Operations Research, 1985, 33 (2): 363- 377. doi: 10.1287/opre.33.2.363
3	Cheng T C E , Ng C T , Yuan J J , et al. Single machine scheduling to minimize total weighted tardiness[J]. European Journal of Operational Research, 2005, 165 (2): 423- 443. doi: 10.1016/j.ejor.2004.04.013
4	Yuan J J , Cheng T C E , Ng C T . NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time[J]. European Journal of Operational Research, 2007, 178 (2): 631- 633. doi: 10.1016/j.ejor.2006.02.014
5	Lawler E L , Moore J M . A functional equation and its application to resource allocation and sequencing problems[J]. Management Science, 1969, 16 (1): 77- 84. doi: 10.1287/mnsc.16.1.77
6	Yue Q , Wan G . Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects[J]. Journal of the Operational Research Society, 2016, 67 (6): 872- 883. doi: 10.1057/jors.2015.107
7	Agnetis A , Mirchandani P B , Pacciarelli D , et al. Scheduling problems with two competing agents[J]. Operations Research, 2004, 52 (2): 229- 242. doi: 10.1287/opre.1030.0092
8	Liu M , Wang S , Zheng F , et al. Algorithms for the joint multitasking scheduling and common due date assignment problem[J]. International Journal of Production Research, 2017, 55 (20): 6052- 6066. doi: 10.1080/00207543.2017.1321804
9	Karhi S , Shabtay D . Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties[J]. International Journal of Production Research, 2018, 56 (9): 3080- 3096. doi: 10.1080/00207543.2017.1400708
10	Wang D , Yu Y , Qiu H , et al. Two-agent scheduling with linear resource-dependent processing times[J]. Naval Research Logistics, 2020, 67 (7): 573- 591. doi: 10.1002/nav.21936
11	陈秋宏, 张新功. 带有固定区间的单机双代理可中断总误工问题[J]. 运筹学学报, 2019, 23 (1): 61- 71. doi: 10.15960/j.cnki.issn.1007-6093.2019.01.007
12	Yang Y J , Yin G Q , Wang C W , et al. Due date assignment and two-agent scheduling under multitasking environment[J]. Journal of Combinatorial Optimization, 2022, 44, 2207- 2223. doi: 10.1007/s10878-020-00600-5
13	Agnetis A, Billaut J-C, Pinedo M, et al. Fifty years of research in scheduling–-theory and applications [J/OL]. (2025-02-07)[2025-02-21]. European Journal of Operational Research. https://www.sciencedirect.com/science/article/pii/S0377221725000773.
14	Pinedo M L . Scheduling Theory, Algorithms and Systems[M]. New York: Springer, 2016.

符号	意义
$ y $	表示当前已经加工工件个数之和, $ y=i+j $
$ t $	表示当前已经加工的$ A $代理中的工件和$ B $代理的非误工工件的加工时间之和
$ x $	表示当前已经加工的$ B $代理的非误工的工件个数
$ e $	表示当前已经加工的$ B $代理的误工工件个数

$ J_{j}^{A} $	$ J_{1}^{A} $	$ J_{2}^{A} $	$ J_{3}^{A} $	$ J_{j}^{B} $	$ J_{1}^{B} $	$ J_{2}^{B} $
$ w_{j}^{A} $	1	2	3	$ p_{j}^{B} $	1	2
$ p_{j}^{A} $	3	4	2	$ d_{j}^{B} $	2	5

符号	意义
$ y $	表示当前已经加工工件个数之和, $ y=i+j $
$ t $	表示当前已经加工的$ A $代理和$ B $代理的工件的加工时间之和
$ T_j $	表示当前已经加工的$ A $代理的误工
$ H_i $	表示当前已经加工的$ B $代理工件的完工时间之和

$ J_{j}^{A} $	$ J_{1}^{A} $	$ J_{2}^{A} $	$ J_{3}^{A} $
$ w_{j}^{A} $	1	2	3
$ p_{j}^{A} $	3	4	2

[1]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[8]	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.
[9]	Qiiong WU, Changjun WANG. Production capacity sharing bargaining based on Lagrangian relaxation [J]. Operations Research Transactions, 2024, 28(2): 93-102.
[10]	Shengxue HE. Transit vehicle scheduling model and 3M evolutionary algorithm based on super spatiotemporal network [J]. Operations Research Transactions, 2023, 27(3): 68-82.
[11]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[12]	Wei XU, Yuefeng HUANG, Caihua CHEN. Charging and discharging scheduling for electric bus charging station with energy storage system [J]. Operations Research Transactions, 2023, 27(2): 95-109.
[13]	Jing YU, Zhe XU, Fang XIE. A branch and bound method for project scheduling problem with activities overlapping [J]. Operations Research Transactions, 2023, 27(1): 115-126.
[14]	WAN Long, HUANG Xiaoli, MEI Jiajie. Scheduling with periodic due date to minimize the maximum tardiness [J]. Operations Research Transactions, 2022, 26(4): 75-86.
[15]	Mingyang GONG, Zhiyi TAN, Yujie YAN. On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria [J]. Operations Research Transactions, 2022, 26(3): 92-108.

Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 14

Related Articles 15

Recommended Articles

Metrics

Comments