English

运筹学学报 >

2022 , Vol. 26 >Issue 3: 151 - 156

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

极大化提前完工总量平行机排序问题的LPT算法

展开
  • 1. 浙江商业职业技术学院人文学院, 浙江杭州 310053
    2. 浙江工商大学管理工程与电子商务学院, 浙江杭州 310018
蒋义伟, E-mail: jywzju@163.com

收稿日期: 2022-01-20

  网络出版日期: 2022-09-07

基金资助

浙江省教育厅高校国内访问学者"教师专业发展项目"(FX2020093);国家自然科学基金(11971434);国家自然科学基金(11871327)

收起

LPT heuristic for parallel-machine scheduling of maximizing total early work

Expand
  • 1. College of Humanities, Zhejiang Business College, Hangzhou 310053, Zhejiang, China
    2. School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, Zhejiang, China

Received date: 2022-01-20

  Online published: 2022-09-07

Fold

摘要

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。

关键词： 平行机排序; LPT算法; 最坏情况界; 提前完工总量

本文引用格式

周萍, 季敏, 蒋义伟 . 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022 , 26(3) : 151 -156 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.012

Abstract

This paper considers the problem of scheduling on three identical machines with a common due date. The preemption is not allowed. The goal is to maximize the total early work of all the jobs, i.e., the total processing time of all the jobs (or part) completed before the common due date. Since the problem is NP-hard, we apply the classical heuristic, namely longest processing time (LPT), to tackle the problem. We show that the worst-case ratio of LPT is at most $\frac{15}{13}$ and the lower bound of the worst-case ratio is at least $\frac{27}{25}$ by providing an instance.

Key words： parallel-machine scheduling; LPT heuristic; worst-case ratio; total early work

参考文献

1 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.
2 Sterna M . A survey of scheduling problems with late work criteria[J]. Omega, 2011, 39 (2): 120- 129.
3 Sterna M . Late and early work scheduling: A survey[J]. Omega, 2021, 104, 102453.
4 Wu C , Yin Y , Wu W , et al. Using a branch and bound and a genetic algorithm for a single machine total late work scheduling problem[J]. Soft Computing, 2016, 20 (4): 1329- 1339.
5 Zhang X G , Wang Y . Two-agent scheduling problems on a single-machine to minimize the total weighted late work[J]. Journal of Combinatorial Optimization, 2017, 33 (3): 945- 955.
6 Wang D J , Kang C C , Shiau Y R , et al. A two-agent single machine scheduling problem with late work criteria[J]. Soft Computing, 2017, 21 (8): 2015- 2033.
7 Potts C N , Van Wassenhove L N . Single machine scheduling to minimize total late work[J]. Operations Research, 1992, 40 (3): 586- 595.
8 Potts C N , Van Wassenhove L N . Approximation algorithms for scheduling a single machine to minimize total late work[J]. Operations Research Letters, 1992, 11 (5): 261- 266.
9 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.
10 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.
11 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.
12 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.
Options
文章导航

/

〈 〉