可中断的多任务平行机排序问题

运筹学学报 ›› 2013, Vol. 17 ›› Issue (3): 115-123.

可中断的多任务平行机排序问题

仲维亚^1,*，马文慧¹，霍志明¹

1. 上海大学理学院数学系, 上海, 200444

出版日期:2013-09-15 发布日期:2013-09-15
通讯作者: 仲维亚 E-mail:wyzhong@shu.edu.cn
基金资助:
上海大学第六届研究生创新基金项目

A preemptive multiprocessor order parallel machine scheduling problem

ZHONG Weiya^1,*, MA Wenhui¹, HUO Zhiming¹

1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Online:2013-09-15 Published:2013-09-15

摘要/Abstract

摘要： Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.

关键词: 排序, 近似算法, NP-难

Abstract: Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51) study the following problem: there are n orders each of which requests various quantities of the different product types. All the orders are available for processing at time t=0, and preemption is allowed. Order i has a weight \omega_{i} and its completion time is the time when its last requested product type is completed. The goal is to find a preemptive schedule such that the total weighted completion time \sum\limits_{i=1}^n\omega_{i}C_{i} is minimized. They show that this problem is NP-hard and propose a heuristic with worst-case ratio analysis. When reading the proof of Theorem 2 in this paper, we find that some statements are not correct. In this paper, we show that although the proof of Theorem 2 is not valid, the conclusion is still right. Furthermore, we propose an improved approximation algorithm for a special case.

Key words: scheduling, approximation algorithm, NP-hard

中图分类号:

O223

仲维亚，马文慧，霍志明. 可中断的多任务平行机排序问题[J]. 运筹学学报, 2013, 17(3): 115-123.

ZHONG Weiya, MA Wenhui, HUO Zhiming. A preemptive multiprocessor order parallel machine scheduling problem[J]. Operations Research Transactions, 2013, 17(3): 115-123.

参考文献

Leung J Y T, Lee C Y, Ng C W, et al. Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51.
Blocher J D, Chhajed D. The customer order lead-time problem on parallel machines [J]. Naval Research Logistics, 1996, 43: 629-654.
Yang J, Posner M E. Scheduling parallel machines for the customer order problem [J]. Journal of Scheduling, 2005, 8: 49-74.
Jr C E G, Nozari A, Yannakakis M. Optimal scheduling of products with two subassemblies on a single machine [J]. Operations Research, 1989, 37: 426-436.
Gerodimos A E, Glass C A, Potts C N, et al. Scheduling multi-operation jobs on a single machine [J]. Annals of Operations Research, 1999, 92: 87-105.
Gupta J N D, Ho J C, Veen A A. Single machine hierarchical scheduling with customer orders and multiple job classes [J]. Annals of Operations Research, 1997, 70: 127-143.
Julien F M, Magazine M J. Scheduling customer orders: An alternative production scheduling approach [J]. Journal of Manufacturing Operation Management, 1990, 3: 177-199.
Ng C T, Cheng T C E, Yuan J J. Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem [J]. Information Processing Letters, 2002, 82: 187-191.
Leung J Y-T, Li H, Pinedo M. Order scheduling in an environment with dedicated resources in parallel [J]. Journal of Scheduling, 2005, 8: 355-386.
Leung J Y-T, Li H, Pinedo M, et al. Open shops with jobs overlap-revisited [J]. European Journal of Operational Research, 2005, 163: 569-571.
Roemer T A. A note on the complexity of the concurrent open shop problem [J]. Journal of Scheduling, 2006, 9: 389-396.
Sung C S, Yoon S H. Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines [J]. International Journal of Production Economics, 1998, 54: 247-255.
Wagneur E, Sriskandarajah C. Open shops with jobs overlap [J]. European Journal of Operational Research, 1993, 71: 366-378.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[3]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[4]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[5]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[6]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[7]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[8]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[9]	仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74.
[10]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[11]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[12]	赵晓成, 李大刚. 机器和工人都有加工资质约束的平行机排序问题研究[J]. 运筹学学报, 2018, 22(3): 99-108.
[13]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[14]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[15]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.