摘要
研究带批运输的两台同型机排序问题.在该问题中,工件在两台同型机上加工,完工的工件由一辆容量为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＋ε.
出处
《运筹学学报》
CSCD
北大核心
2013年第1期38-43,共6页
Operations Research Transactions
基金
国家自然科学基金资助项目(No.11171106)
关键词
排序
批运输
近似算法
scheduling, batch delivery, approximation algorithm
