Multidimensional(Multiple) Task Scheduling Problem With Rejection Cost

Scheduling problem is one of the most concern problem in the field of combinato-rial optimization.It applies in the fields of industrial production,logistics scheduling,facility location and so on.In most of the literature on scheduling problems,it is re-quired that all tasks must be scheduled on the machine.The goal is to find a suitable solution that minimizes the makespan of machines.Subsequently,many researchers proposed and studied the scheduling problem with rejection cost.The difference be-tween scheduling problems with rejection cost and classic scheduling problems is that all tasks do not be required to assign to the machines.Each task is either accepted and and then assigned to one machine,or rejected with penalty costs.The goal is to find a suitable solution that minimizes the sum of the makespan and the rejection cost of all rejected tasks.Based on the study of the scheduling problems with rejection cost,we propose the multidimensional task scheduling with rejection on a single machine in section three.We prove the problem is NP-hard by 2-partition problem and give a d-approximation algorithm in O?nd?.We design a fully polynomial time approximation scheme with constant d,whose running time is O(n^d+1?d/??^d).We address a randomized algorithm with 1.585-approximation.In addition,for the unknown information about multidimen-sional tasks,we propose an online algorithm which competitive is d.In section four,we propose a multiple task scheduling problem with rejection,we give a 2-approximation algorithm in O?n²logn?.We address a fully polynomial time approximation scheme for the constant m,which is solved in O(?4/??^m?ntmax?^m+1),where tmax is the maximum number of tasks for all users,?is an arbitrary positive number.When the information of users is unknown,we propose an online algorithm whose competitive is 2.618.More-over,for m=2 we give a 1.618-competitive algorithm,which is the best possible.Using Matlab programming to achieve the output solution of the algorithm in the two sections,using Cplex to calculate the optimal solution of the corresponding instance,compare the two function values,the experimental results are represented by a bar graph.The last section summarizes all the research results of this paper and proposes future research directions.