文献类型：期刊文献

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

英文题名：An improved algorithm for scheduling two identical machines with batch delivery consideration

作者：汪磊扬[1];刘朝晖[1]

机构：[1]华东理工大学数学系,上海200237

年份：2013

卷号：17

期号：1

起止页码：38

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;北大核心:【北大核心2011】；CSCD:【CSCD2013_2014】；

基金：国家自然科学基金资助项目(No.11171106)

语种：中文

中文关键词：排序;批运输;近似算法

外文关键词：scheduling, batch delivery, approximation algorithm

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