A Class Of Single Machine Scheduling Problem With Primary And Secondary Indicators

For single machine primary-secondary criteria scheduling problems, there are three open problems which all have ?Uj as one of the criteria. The problems studied in this paper are two polynomially solvable subcases about one of the three problems, which can be stated as follows:1. Single machine scheduling to minimize the number of tardy jobs with the maximum tardiness being minimized first, subject to the job system with the jobs" processing times being agreeable with their due dates.2. Single machine scheduling to minimize the number of tardy jobs with the maximum tardiness being minimized first, subject to the job system with identical processing times and the jobs' release dates being agreeable with their due dates.1. A subproblem of problem Tmax with the jobs' processing times being agreeable with their due datesIn chapter 2, a polynomial-time algorithm for this subproblem is found. So the subproblem is P-problem.Algorithm 1 1 | agreeable, prmp Tmax(i) Sequence the jobs in EDD order such that(ii) If pi < d], let Ji start work unpremptively at time 0, otherwise, schedule it from time d1+Tmax* -p1 to time d1+Tmax*.(in) Suppose that J1, J2,......, Ji (i