Resource Allocation Scheduling Problems Wieh Job-Rejection

This article studies the single machine scheduling problems with job-rejection and resource allocation.The actual processing time of the jobs can be expressed as a linear function and a convex function of the resource.Under job-rejection,there are two objective costs,i.e.,the processing times cost of the set of processed jobs,and the rejection cost of the set of rejected jobs.The main contents of this paper are given as follows:The first chapter introduces the derivation and development of the scheduling problems in combinatorial optimization,the research background and significance of the scheduling problems with job-rejection and resource allocation.The second and third chapter respectively studies linear and convex resource constraint scheduling problems with job-rejection and deterioration effects.Under the constraint that the jobs have past-sequence-dependent setup times,for the different deterioration factors,the assignment problem is proposed to solve the weighted sum of processing times cost(including makespan(the total completion time,the total absolute differences in completion times,the total absolute differences in waiting times)and the resource consumption cost of the accepted jobs)and total rejection cost of the rejected jobs.If the deterioration factors are identical,the dynamic programming algorithm is used to minimize the following problem:1)The weighted sum of the processing times cost and rejection cost of the sets of processed and rejected jobs,and the algorithm complexity is O(n3),where n is the total number of the jobs;2)The problem of minimizing the processing times cost subject to a constraint on the maximal rejection cost;3)The problem of minimizing the rejection cost given that the processing times cost cannot exceed a known upper bound.For the NP-hard problems of 2)and 3),we introduce the pseudo-polynomial dynamic programming algorithms,respectively,and algorithm complexities are O n3E and O(n3T),where E and T are given constants.Under different and identical deterioration factors,the numerical simulations are given,experimental results show that the algorithms are very effective.The fourth chapter focuses on the conclusion and outlook,and the research contents of the paper are summarized and prospected.