提前完工总量最大化问题的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算法

孙瑞卿¹, 张芮², 兰艳^2,†, 李伟东¹

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

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

LPT algorithm for early work maximization problem

SUN Ruiqing¹, ZHANG Rui², LAN Yan^2,†, LI Weidong¹

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 Published:2025-12-11

摘要/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.

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

参考文献

[1] Sterna M. A survey of scheduling problems with late work criteria [J]. Omega, 2011, 39(2): 120-129.
[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.
[4] Sterna M. Late and early work scheduling: A survey [J]. Omega, 2021, 104: 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.
[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.
[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.
[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.
[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.

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

LPT algorithm for early work maximization problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[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.