提前完工总量最大化问题的LPT算法

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

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

• 论文 • 上一篇

提前完工总量最大化问题的LPT算法

孙瑞卿¹, 张芮², 兰艳²^,*(), 李伟东¹

1. 云南大学数学与统计学院, 云南昆明 650504
2. 大连民族大学信息与通信工程学院, 辽宁大连 116600

收稿日期:2023-01-27 出版日期:2025-12-15 发布日期:2025-12-11
通讯作者: 兰艳 E-mail:lanyan@dlnu.edu.cn
基金资助:
国家自然科学基金(12071417)

LPT algorithm for early work maximization problem

Ruiqing SUN¹, Rui ZHANG², Yan LAN²^,*(), Weidong LI¹

1. School of Mathematics and Statistics, Yunnan University, Kunming 650504, Yunnan, China
2. School of Information and Communication Engineering, Dalian Minzu University, Dalian 116600, Liaoning, China

Received:2023-01-27 Online:2025-12-15 Published:2025-12-11
Contact: Yan LAN E-mail:lanyan@dlnu.edu.cn

摘要/Abstract

摘要：

本文给定一个工件集和一个机器集, 将每一个工件分配给机器加工, 不允许中断。提前完工总量最大化问题试图寻找一个最佳调度方案, 使得所有工件的提前完工总量尽可能地大, 这里工件的提前完工量是指交货期前工件的已加工时长。本文证明了经典的LPT算法的最坏情况界至多为1.207。

关键词: 调度, 提前完工总量, 最坏情况界, LPT算法

Abstract:

For a given set of jobs and a given set of machines, we assign the jobs to the machines without preemption. The early work maximization problem tries to find a schedule such that the total early work of the jobs is maximized, where the early work of a job is the processed time before the common due date. We prove that the worse-case ratio of LPT algorithm is at most 1.207.

Key words: scheduling, total early work, worse-case ratio, LPT algorithm

中图分类号:

O221.2

孙瑞卿, 张芮, 兰艳, 李伟东. 提前完工总量最大化问题的LPT算法[J]. 运筹学学报（中英文）, 2025, 29(4): 249-254.

Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem[J]. Operations Research Transactions, 2025, 29(4): 249-254.

参考文献 15

1	Sterna M . A survey of scheduling problems with late work criteria[J]. Omega, 2011, 39 (2): 120- 129. doi: 10.1016/j.omega.2010.06.006
2	Błażewicz J . Scheduling preemptible tasks on parallel processors with information loss[J]. Technique et Science Informatiques, 1984, 3 (6): 415- 420.
3	Sterna M , Czerniachowska K . Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work[J]. Journal of Optimization Theory and Applications, 2017, 174 (3): 927- 944. doi: 10.1007/s10957-017-1147-7
4	Sterna M . Late and early work scheduling: A survey[J]. Omega, 2021, 104, 102453. doi: 10.1016/j.omega.2021.102453
5	Chen X , Wang W , Xie P , et al. Exact and heuristic algorithms for scheduling on two identical machines with early work maximization[J]. Computers & Industrial Engineering, 2020, 144, 106449.
6	Jiang Y , Guan L , Zhang K , et al. A note on scheduling on two identical machines with early work maximization[J]. Computers & Industrial Engineering, 2021, 153, 107091.
7	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26 (3): 151- 156. doi: 10.15960/j.cnki.issn.1007-6093.2022.03.012
8	Chen X , Liang Y , Sterna M , et al. Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date[J]. European Journal of Operational Research, 2020, 284 (1): 67- 74. doi: 10.1016/j.ejor.2019.12.003
9	Li W . Improved approximation schemes for early work scheduling on identical parallel machines with a common due date[J]. Journal of the Operations Research Society of China, 2024, 12, 341- 350.
10	Györgyi P , Kis T . A common approximation framework for early work, late work, and resource leveling problems[J]. European Journal of Operational Research, 2020, 286 (1): 129- 137. doi: 10.1016/j.ejor.2020.03.032
11	Chen X , Sterna M , Han X , et al. Scheduling on parallel identical machines with late work criterion: Offline and online cases[J]. Journal of Scheduling, 2016, 19 (6): 729- 736.
12	Chen X , Kovalev S , Liu Y , et al. Semi-online scheduling on two identical machines with a common due date to maximize total early work[J]. Discrete Applied Mathematics, 2021, 290, 71- 78. doi: 10.1016/j.dam.2020.05.023
13	Xiao M, Liu X, Li W. Semi-online early work maximization problem on two hierarchical machines with partial information of processing time[C]//International Conference on Algorithmic Applications in Management. Dallas: Springer, 2021: 146-156.
14	Xiao M, Liu X, Li W, et al. Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work[EB/OL]. [2023-01-01]. arXiv: 2209.08704.
15	Xiao M, Bai X, Li W. Online early work maximization problem on two hierarchical machines with buffer or rearrangements[C]//International Conference on Algorithmic Applications in Management. Cham: Springer, 2022: 46-54.

[1]	靳凯媛, 郑斐峰, 刘明. 考虑订单类型和准备时间的批处理机在线调度模型研究[J]. 运筹学学报（中英文）, 2025, 29(4): 231-240.
[2]	万国华, 王杉, 黄腾方. 服务系统中的预约调度: 综述及扩展[J]. 运筹学学报（中英文）, 2025, 29(3): 61-76.
[3]	鲁炜, 卢星宇, 邹丁, 陈博晓, 周义涵, 张国川. 绿色计算下算力调度优化问题与技术研究[J]. 运筹学学报（中英文）, 2025, 29(3): 179-201.
[4]	郭思琦, 周萍, 蒋义伟, 季敏. 考虑碳排放成本的计件维护单机调度问题[J]. 运筹学学报（中英文）, 2025, 29(2): 68-79.
[5]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[6]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[7]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[8]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[9]	何胜学. 基于超级时空网络的公交车辆调度模型及3M进化算法[J]. 运筹学学报, 2023, 27(3): 68-82.
[10]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.
[11]	于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.
[12]	万龙, 黄晓莉, 梅嘉杰. PDD规则下最小化最大延误调度问题[J]. 运筹学学报, 2022, 26(4): 75-86.
[13]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[14]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[15]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.

提前完工总量最大化问题的LPT算法

LPT algorithm for early work maximization problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价