English

运筹学学报 >

2025 , Vol. 29 >Issue 4: 249 - 254

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

论文

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

  • 孙瑞卿 ,
  • 张芮 ,
  • 兰艳 ,
  • 李伟东
展开
  • 1. 云南大学数学与统计学院, 云南昆明 650504
    2. 大连民族大学信息与通信工程学院, 辽宁大连 116600
兰艳  E-mail: lanyan@dlnu.edu.cn

收稿日期: 2023-01-27

  网络出版日期: 2025-12-11

基金资助

国家自然科学基金(12071417)

版权

运筹学学报编辑部, 2025, 版权所有，未经授权，不得转载。
收起

LPT algorithm for early work maximization problem

  • Ruiqing SUN ,
  • Rui ZHANG ,
  • Yan LAN ,
  • Weidong LI
Expand
  • 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 date: 2023-01-27

  Online published: 2025-12-11

Copyright

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

摘要

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

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

本文引用格式

孙瑞卿 , 张芮 , 兰艳 , 李伟东 . 提前完工总量最大化问题的LPT算法[J]. 运筹学学报, 2025 , 29(4) : 249 -254 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.020

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

参考文献

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.
Options
文章导航

/

〈 〉