讲座标题：An New Approximation Algorithm for Single Machine Scheduling with Rejection and Release Dates Using Linear Programming
主讲人： 刘培海 副教授
讲座时间：12月17号（周日）下午13:30-14:30
讲座语言：中文，英文
主办单位：数学学院
讲座内容：
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.
主讲人简介：
刘培海 副教授 华东理工大学