工件带拒绝费用的三台单机排序问题研究  

Three single-machine scheduling problem with rejection cost

作　　者：魏飞[1] 刘守鹏[1] 

机构地区：[1]滨州医学院,山东烟台264003

出　　处：《山东科学》2013年第6期9-13,共5页Shandong Science

基　　金：国家自然科学基金(11001117)

摘　　要：本文对带拒绝费用的排序问题进行了研究,目标是极小化接受工件的最大完工时间与拒绝工件的总拒绝费用之和。对于一种三台机器的特殊情况,提出了一个新的在线算法,并对新算法的竞赛比进行了分析。Our objective is to minimize the sum of the makespan of the accepeted jobs and the total rejection cost of the rejected jobs.We present a new on-line algorithm for a special case of three machines.We also analyze its competitive ratio.

关 键 词：在线排序 竞赛比 同类机 

分 类 号：O223[理学—运筹学与控制论]