带批运输的两台同型机排序问题的改进算法

运筹学学报 ›› 2013, Vol. 17 ›› Issue (1): 38-43.

带批运输的两台同型机排序问题的改进算法

汪磊扬¹，刘朝晖¹

1. 华东理工大学数学系

出版日期:2013-03-15 发布日期:2013-03-15
通讯作者: 刘朝晖 E-mail:zhliu@ecust.edu.cn
基金资助:
国家自然科学基金资助项目(No. 11171106)

An improved algorithm for scheduling two identical machines with batch delivery consideration

WANG Leiyang¹, LIU Zhaohui¹

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

Online:2013-03-15 Published:2013-03-15

摘要/Abstract

摘要： 研究带批运输的两台同型机排序问题. 在该问题中，工件在两台同型机上加工，完工的工件由一辆容量为z的车运输到客户. 这里假设工件有不同的物理大小，目标是求一个时间表使得所有工件送达客户且车回到机器所在位置的时间最小，给出了一个(14/9+ε)-近似算法

关键词: 排序, 批运输, 近似算法

Abstract: In this paper we consider the scheduling problem on two identical (parallel) machines in which the finished jobs need to be delivered to a customer in batches by single vehicle. The goal is to minimize the makespan, i.e., the time by which the vehicle has delivered the last job and returned to the machines. We assume that the jobs have different sizes, and give an approximation algorithm with the worst-case performance ratio(14/9+ε).

Key words: scheduling, batch delivery, approximation algorithm

汪磊扬，刘朝晖. 带批运输的两台同型机排序问题的改进算法[J]. 运筹学学报, 2013, 17(1): 38-43.

WANG Leiyang, LIU Zhaohui. An improved algorithm for scheduling two identical machines with batch delivery consideration[J]. Operations Research Transactions, 2013, 17(1): 38-43.

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