讲座标题：An New Approximation Algorithm for Single Machine Scheduling with Rejection and Release Dates Using Linear Programming
主讲人： 刘培海 副教授
In this paper we consider a single machine scheduling problem with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by a single machine, or rejected and then a rejection penalty is paid. The objective is to minimize the completion time of the last accepted job plus the total penalty of all rejected jobs. Using linear programing, we obtain an optimal solution for a relaxation problem, in which a job can be rejected partially. By rounding this solution to a feasible solution for the original problem, we get a 4/3 approximation algorithm.
刘培海 副教授 华东理工大学