Approximation Algorithms For Machine Scheduling Problems With Submodular Rejection Penalties

The multi-machine scheduling problem is one of the most classical combinatorial optimization problems.In this thesis,we study two variants of multi-machine schedul-ing problem—the multi-machine scheduling problem with release dates and submodular rejection penalties,and the multi-machine customer order scheduling with delivery time and submodular rejection penalties.In the multi-machine scheduling problem with release dates and submodular rejection penalties,we are given a set of m identical parallel machines M={M₁,M₂,···,M_m}and a set of n jobs J={J₁,J₂,···,J_n}.Each job has a corresponding processing time and a release date.Letπ:2^J→R_≥0 be a submodular penalty function.The objective is to choose a rejected job set R,and schedule jobs in J\R on the machines such that the sum of the makespan of the accepted jobs and the penalty costπ（R）of the rejected job set is minimized.This thesis presents a 2-approximation algorithm for solving the problem.In this algorithm,we first use the primal-dual scheme to determine the rejected job set and accepted job set,and then schedule the accepted jobs on the machines using the earliest release date rule.In the multi-machine order scheduling problem with delivery time and submodular rejection penalties,we are given a set of m dedicated machines M={M₁,M₂,···,M_m}in parallel and a set of n customer orders O={O₁,O₂,···,O_n}.Each order has a corresponding delivery time and consists of m product types.Each product type has a corresponding processing time and has to be manufactured on the dedicated machine.Let E:2^O→R_≥0 be a submodular penalty function.The objective is to choose a rejected order set R,and schedule orders in O\R on the dedicated machines such that the sum of the maximum delivery completion time of the accepted orders and the penalty cost E（R）of the rejected order set is minimized.In this thesis,we design two approximation algorithms for solving this problem:one is an（n+1）-approximation algorithm based on linear programming rounding technique,and the other is a 2-approximation algorithm based on Lovász rounding technique.In the above algorithms,we first give the integer programming of the problem and relax it into a linear programming,and then obtain the optimal solution of the linear programming and round it to get the rejected order set.Finally,we schedule the accepted orders on the machines using the largest delivery time rule.