带有拒绝的单机和同型机排序问题

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 1-10.

• 运筹学 • 下一篇

带有拒绝的单机和同型机排序问题

高强¹, 鲁习文^1,*

1. 华东理工大学理学院数学系, 上海 200237

收稿日期:2014-05-23 出版日期:2014-12-15 发布日期:2014-12-15
通讯作者: 鲁习文 E-mail:xwlu@ecust.edu.cn
基金资助:
国家自然科学基金(No. 11371137)

Scheduling on single machine and identical machines with rejection

GAO Qiang¹, LU Xiwen^1,*

1. Department of Mathematics, College of Science, East China University of Science and Technology, Shanghai 200237, China

Received:2014-05-23 Online:2014-12-15 Published:2014-12-15

摘要/Abstract

摘要： 研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的\alpha倍. 如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的. 如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的. 对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和. 针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.

关键词: 排序, 可拒绝, 在线算法, 竞争比

Abstract: We consider scheduling problems with rejection for both single machine and identical machines in this paper. For the single machine problems, each job has penalty \alpha times of its processing time. If jobs have release dates, the problem of minimizing the sum of makespan and total penalty can be solved in polynomial time. If all jobs arrive at time zero, the problem of minimizing the sum of total completion time and total penalty also can be solved in polynomial time. For the identical machines problems, jobs arrive over time at two different time points. The objective is to minimize the sum of makespan and total penalty. We design on-line approximation algorithms with competitive ratios 2 or 4-2/m for the two cases when the number of machines is two or m, respectively.

Key words: scheduling, rejection, on-line algorithm, competitive ratio

中图分类号:

O223

高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.

GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection[J]. Operations Research Transactions, 2014, 18(4): 1-10.

参考文献

Zhang L, Lu L, Yuan J. Single machine scheduling with release dates and rejection [J]. European Journal of Operational Research, 2009, 198: 975-978.

Lu L, Ng C T, Zhang L. Optimal algorithms for single-machine scheduling with rejection to minimize the makespan [J]. International Journal of Production Economics, 2011, 130: 153-158.

Cao Z, Zhang Y. Scheduling with rejection and non-identical job arrivals [J]. Journal of Systems Science and Complexity, 2007, 20: 529-535.

Engels D W, Karger D R, Kolliopoulos S G, et al. Techniques for scheduling with rejection [J]. Journal of Algorithms, 2003, 49: 175-191.

Epstein L, Noga J, Woeginger G J. On-line scheduling of unit time jobs with rejection: minimizing the total completion time [J]. Operations Research Letters, 2002, 30: 415-420.

Ma R, Yuan J. Online scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost [J]. Information Processing Letters, 2013, 113: 593-598.

Lu L, Zhang L, Yuan J. The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan [J]. Theoretical Computer Science, 2008, 396: 283-289.

Lu L, Cheng T C E, Yuan J, et al. Bounded single-machine

parallel-batch scheduling with release dates and rejection [J]. Computers & Operations Research, 2009, 36: 2748-2751.

Bartal Y, Leonardi S, Marchetti-Spaccamela A, et al. Multiprocessor scheduling with rejection [J]. SIAM Journal on Discrete Mathematics, 2000, 13: 64-78.

He Y, Min X. On-line uniform machine scheduling with rejection [J]. Computing, 2000, 65: 1-12.

D\'osa G, He Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines [J]. Computing, 2006, 76: 149-164.

Lenstra J K, Rinnooy Kan A H G, Brucker P. Complexity of machine scheduling problems [J]. Annals of Discrete Mathematics, 1977, 1: 343-362.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[3]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[4]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[5]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[6]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[7]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[8]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[9]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[10]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[11]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[12]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[13]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[14]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[15]	张龙, 张玉忠, 柏庆国. 一类博弈排序问题的纳什均衡存在性证明 [J]. 运筹学学报, 2018, 22(1): 87-96.

带有拒绝的单机和同型机排序问题

Scheduling on single machine and identical machines with rejection

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价