Scheduling Problems With Variable Unavailable Interval And Rejection

Most literature in scheduling problems assumes that machines are available all the time.However,this availability may not be true in real industry setting.In this thesis,we consider that the machine is not always be available,that is,the machine has an unavailable interval.There are two models of the unavailable interval:one is that the machine has a variable maintenance;the other is that the machine has an operator non-availability period.The job can't be processed during an unavailable interval,the starting time of the maintenance interval is known and fixed in advance,the maintenance duration is a non-negative and non-decreasing function of the machine's workload before the maintenance activity.In contrast to a variable maintenance,the job can be processed,but can neither start nor complete during the operator unavailable period.Moreover,the job with rejection means that each job may be either accepted and processed on the machine,or be rejected and paid the.corresponding cost.In this thesis,we firstly investigate two single.machine scheduling problems under the condition of a variable maintenance duration and rejection,subsequently we investigate the single-machine scheduling problem under the condition of operator non-availability period and rejection.The main contents in our research can be divided into three parts.In the first part,we discuss single-machine scheduling problem with a variable maintenance duration and jobs with rejection and the identical release date.In the second part,we study single-machine scheduling problem with a variable maintenance duration and jobs with rejection and the non-identical release dates.In the third part,we study the single-machine scheduling problem with an operator non-availability period and rejection.We use h1 to denote the restriction that there is a variable unavailable interval during the processing on the machine,and we use ona(1)to denote the restriction that there is an operator non-availability interval during the processing on the machine,and we use wldmt to indicate the maintenance duration is related to the machine load,also we use reject to indicate that the jobs is allowed to be rejected.In Chapter 2,we study the following scheduling problem:Single-machine problem with the identical release date to minimize the sum of the makespan of the scheduled jobs and the total rejection cost of the rejected jobs:1,h1,wldmt|reject|Cmax(A)+W(R)For the above problem,we present a dynamic programming algorithm in Section 2.2.in Section 2.3,we present an approximation algorithm and prove that the worst-case ratio is 2.In Section 2.4,we present a fully polynomial time approximation scheme under a special circumstance.In Chapter 3,we study the following scheduling problem:Single-machine problem the non-identical release date to minimize the sum of the makespan of the scheduled jobs and the total rejection cost of the rejected jobs:1,h1:wldrmt|rj,reject|Cmax(A)+ W(R)For the above problem,we present a dynamic programming algorithm in Section 3.2.In Section 3.3,we present an approximation algorithm and prove that the worst-case ratio is 3.In Chapter 4,we study the following scheduling problem:Single-machine scheduling problem with an operator non-availability period and rejection to minimize the sum of the makespan of the scheduled jobs and the total rejection cost of the rejected jobs:1|ona(1),reJect|Cmax(A)+ W(R)For the above problem,we present an approximation algorithm and prove that the worst-case ratio is 2 in Section 4.2.