Single-machine Rescheduling Problems With Rejection

In this thesis,we consider some single machine rescheduling problems in which the new job can be rejected.Assuming that a set of original jobs has al-ready been scheduled for processing.However,before they are processed,a set of new jobs arrives.Thus,the manufacturer needs to reschedule all jobs at this time,i.e.He will insert the new jobs into the existing original schedule.It will delay the processing positions and the starting times of the original jobs.In order to guarantee to the original jobs'demand,the sequence or time disruption of the original jobs is not greater than a given upper bound6).This thesis studies some single-machine rescheduling problems which they need to satisfied the sequence or time disruption constraint.Furthermore,we also assume that job rejection is allowed.That is,if a job is rejected,we need to pay a corresponding rejection cost.The goal is to minimize the sum of a given objective function1)and the total rejection cost.Here we assume that only the new jobs can be rejected and???.We also put the disruptionas a constraint objective and???.Here D_maxis the maximum sequence dis-ruption of the original jobs,?D_j is the total sequence disruption of the original jobs,?_maxis the maximum time disruption of the original jobs and ??_j is the total time disruption of the original jobs.On the basis we combine the reschedul-ing problems with new jobs'rejection costs.We use rej to denote the constraint that only new jobs can be rejected and use ??k to denote the constraint than the disruption ? of the original jobs cannot exceed k.The corresponding problem can be denoted by ???.?1?In Chapter 2,in view of the scheduling problem ???.When ?=0,all accepted new jobs can be processed after the original jobs.Thus,all problems ??? can be solved in polynomial-time.When rj?0,we show that this problem is binary NP-hard and then present a dynamic programming algorithm.Furthermore,we also present a 2-approximation algorithm and an FPTAS.?2?In Chapter 3,we consider the rescheduling problem ???.For each problem ???,when ??{?_max,??_j},we finally show that each problem is binary NP-hard and give a pseudo poly-nomial time algorithm.when ??{D_max,?D_j},we present a polynomial time algorithm.?3?In Chapter 4,we study the scheduling problem ???.When ??{D_max,?_max,?D_j},we show that each problem 1??? is binary NP-hard and then present a dynamic programming algorithm.However,when ?=??_j,problem ??? is strongly NP-hard.Thus,for this question there is no pseudo-polynomial-time algorithm for the latter problem.