Research On Scheduling With Job-rejection And Two-agent Under The Total Late Work Criterion

In the research of classical scheduling problems, all the jobs must be processed on the machines. However, in practical applications, for the sake of reducing manufacturing costs and obtaining maximum profits, the manufacturer usually rejects some jobs which have larger processing times and bring relatively small profits. If the job is rejected by the manufacturer, then a corresponding rejection cost has to be paid. If a job is accepted by the manufacturer, then this job must be processed on the machine and a corresponding production cost needs be paid. In this thesis, under the job-rejection assumption, we study the scheduling problems for minimizing the total late work pius the total rejection cost. Besides, considering the case that multiple agents may compete for the processing resources on the same machine in reality, we also study two-agent constrained scheduling problems, and our goal is to minimize one agent's objective value under the constraint that the other agent's objective value is restricted.This thesis is divided into two parts to the scheduling problems with job-rejection for minimizing the total late work plus the total rejection cost and the two-agent constrained scheduling problems, respectively. In the first part, we study the scheduling problems for minimizing the (weighted) total late work plus the total rejection cost under the two assumptions of the processing of the jobs: with or without preemption. In the second part,the jobs are of preemptive, and our goal is to minimize one agent's scheduling cost under the constraint that the other agent's total late work is less than or equal a threshold value.The main results of this thesis are as follows:·We show that the scheduling problem 1 | rej,pmtn, dj = d|Y + ?j?Rej is NP-hard,and then we point out that the scheduling problem 1|rej,pmtn |Y+?j?Rej has O(n?pj)- and O(n?ej)-time algorithms and a fully polynomial-time approximation scheme.·For scheduling problem 1 | rej| Y+?j?Rej, we present two pseudo-polynomial-time algorithms and a fully polynomial-time approximation scheme.·For scheduling problem 1| rej,pmtn | Yw + ?j?Rej and 1|rej,dj=d|Yw+?j?Rej,we present a pseudo-polynomial-time algorithms, respectively.·For the two-Lgent constrained scheduling problem 1 | pmtn,YB?Q|YA, we present an O(nA lognA+nBlognB)-time algorithm.·For the two-agent constrained scheduling problem 1| pmtn, YB < Q | fA, we point out that, when fA =YA, the problem is NP-hard and is solvable in a pseudo-polynomial-time, and when fA?{?CjA, fmaxA:?UjA}, the problem is solvable in polynomial time.