Parallel Machines That Consider Delays Can Refuse To Sort

Parallel-machine scheduling problem is a kind of multi-machine scheduling problem, which has an important significance in theory and application. In theory, parallel-machine scheduling problem is a generalization of the single machine scheduling problem. And from the application point of view, its research is closely related to our life, has its extensive applicable background. In this paper, we mainly consider the parallel-machine scheduling problem under the job rejection constraint.In the first chapter, we mainly introduce some background knowledge of scheduling problem, the research development of the scheduling over the years and some related basic knowledge. Then the main research results about this dissertation have been summarized simply.In the second chapter, we mainly study identical parallel-machine scheduling problem with rejection, three models are considered:(1) Identical parallel-machine scheduling problem with release dates and rejection. Under the constraint of the total rejection penalty of the rejected jobs cannot exceed a given upper bound U, the objective is to minimize the makespan of the accepted jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mn(rmax +P)m) time, where m is the number of machines; n is the number of jobs; rmax is the maximum release date; pJ is the processing time of job J J and P=∑1=1n pj is total sum of the processing times of all jobs. Furthermore, we provide a fully polynomial-time approximation scheme for the scheduling problem;(2)Identical parallel-machine scheduling problem with rejection, the objective is to minimize the sum of maximum lateness of the accepted jobs and the total rejection penalty of the rejected jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mnPm∑i=1n Wi) time, where Wj,(j= 1,2,···,n) is the rejection penalty of job Jj(3) Identical parallel-machine scheduling problem with rejection. Under the constraint of the total rejection penalty of the rejected jobs cannot exceed a given upper bound U, the objective is to minimize the maximum lateness of the accepted jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mnUPm) time.In the third chapter, we mainly study the uniform parallel-machine scheduling problem with rejection, four models are considered:(1)Uniform parallel-machine scheduling problem with release dates and rejection, the objective is to minimize the sum of makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mn(rmax+P/bm)m) time, where bi, (i= 1,2, ···, m) is the processing speed of machine Mi;(2)Uniform parallel-machine scheduling problem with release dates and rejection. Under the constraint of the total rejection penalty of the rejected jobs cannot exceed a given upper bound U, the objective is to minimize the makespan of the accepted jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mn(rmax+P/bm)m) time;(3)Uniform parallel-machine scheduling problem with rejection, the objective is to minimize the sum of the maximum lateness of the accepted jobs and the total rejection penalty of the rejected jobs. We can get the optimal value by the dynamic programming algorithm which runs in O{mn{P/bm)m∑i=1nWi) time;(4)Uniform parallel-machine scheduling problem with rejection. Under the constraint of the total rejection penalty of the rejected jobs cannot exceed a given upper bound U, the objective is to minimize the maximum lateness of the accepted jobs. We can get the optimal value by the dynamic programming algorithm which runs in O(mnU(P/bm)m) time.