Parallel Machine Scheduling Problem With Rejection Cost Under Special Conditions

The scheduling problem is a kind of important combinatorial optimization prob-lem.Its purpose is to use some resources to optimally complete a batch of tasks.It plays an important role in many aspects of real life.With the development of modern industry,all kinds of more and more on the study of scheduling problems.Schedul-ing theory has been one of the fastest-growing,most extensively researched,and most fruitful disciplines in the world.The classical parallel machine scheduling problem is a famous NP-hard problem.Unless P=NP,otherwise there is no polynomial-time accurate algorithm for NP-hard problem.Research on this problem has continued for more than 50 years and never stopped.For a more realistic situation,if the processing time of the job is very large and the processing cost is very high,it cannot be processed.The parallel machine scheduling problem with rejection cost arises at the historic moment.In this dissertation,we mainly study the parallel machine scheduling problem with rejection cost and consider the polynomial-time solvability of the problem under some special conditions.For the processing times are powers of 2 or processing times satisfy the divisible property,we design a polynomial-time algorithm that solves the classical scheduling problem.Also,the complexity and approximate ratio of the algorithm on the general classical scheduling problem were analyzed,and corresponding compact examples were provided.For the processing times are powers of 2 and the rejection costs are 1 or 2,the parallel machine scheduling problem with rejection cost is solved by the polynomial-time algorithm based on the greedy,and the proof is given.The polynomial-time algorithm we proposed is based on the bin-packing,which broadens our thinking and provides us with new ideas for studying other problems.