On-line Scheduling with Rejection on Uniform Machines

作     者：Shoupeng Liu Yuzhong Zhang College of Operations Research and Management Science,Qufu Normal University, Rizhao, Shangdong, 276826 

会议名称：《中国运筹学会第七届学术交流会》

会议日期：2004年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：Supported by NSFC 10171054 

关 键 词：On-line scheduling Competitive ratio Uniform machines 

摘      要：In this paper we consider the problem of on-line scheduling of unit exectiontime jobs on uniform machines with rejection *** jobs arrive one by one andcan be either accepted and scheduled, or be rejected. The objective is to minimize thetotal completion time of the accpted jobs and the total penalty of the rejection *** propose an on-line algorithm and prove that the competitive ratio is 1/2(2 +3) ≈1.86602.