文献类型：期刊文献

中文题名：带有拒绝的单机和同型机排序问题

英文题名：Scheduling on single machine and identical machines with rejection

作者：高强[1];鲁习文[1]

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

年份：2014

卷号：18

期号：4

起止页码：1

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

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

基金：国家自然科学基金(No.11371137)

语种：中文

中文关键词：排序;可拒绝;在线算法;竞争比

外文关键词：scheduling, rejection, on-line algorithm, competitive ratio

摘要：研究了带有拒绝的单机和同型机排序问题.对于单机情形,工件的惩罚费用是对应加工时间的α倍.如果工件有到达时间,目标为最小化时间表长与惩罚费用之和,证明了这个问题是可解的.如果所有工件在零时刻到达,目标为最小化总完工时间与惩罚费用之和,也证明了该问题是可解的.对于同型机排序问题,研究了工件分两批在线实时到达的情形,目标为最小化时间表长与惩罚费用之和.针对机器台数2和m,分别给出了竞争比为2和4-2/m的在线算法.
We consider scheduling and identical machines in this paper. penalty α times of its processing time. problems with rejection for both single machine For the single machine problems, each job has If jobs have release dates, the problem of mini- mizing 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 problem- s, 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.