Some Single Machine Scheduling Problems With Rejection

The scheduling problem with rejection is a practical problem with strong application background.In actual production,the manufacturer may choose to reject to process some jobs with high cost,long time or low profit,and pay penalties.In the traditional scheduling problem,the processing time of jobs is always fixed.The processing time of the jobs may change in the production process.Due to the wear of the machine or the change of temperature,the actual processing time of a job is longer if it is scheduled later in a sequence,that is,the deteriorating effect;With the increase of workers’proficiency,the more backward the position of the job is,the shorter the processing time is,that is,the learning effect.The machine is not available for some time due to repair,maintenance or tool replacement,that is,non-availability interval.Therefore,the research on the scheduling problem with rejection and variable processing time is vital to improve productivity,reduce working-in-processing inventories and improve customer satisfactory.This paper mainly studies some single machine scheduling problems with rejection.The content of the dissertation is summarized as follows:1.We consider the single machine scheduling problem with rejected jobs with deadline constraints.The objective is to minimize the sum of the total weighted late work of the accepted jobs and the total rejection penalty of the rejected jobs,where the late work of a job is the amount of processing of the job that is scheduled after its due date.In this scheduling problem,each job has a deadline.Under the constraint of deadline and the same due date of jobs,we show that the single machine scheduling problem of minimizing the sum of weighted total late work and rejection penalty is NP-hard.We also give a pseudo-polynomial-time dynamic programming that runs in O（n ~3d）to solve this problem by enumerating the critical jobs in turn.Finally,a numerical example is given to verify.2.We consider single machine scheduling with deteriorating jobs,rejection and availability constraints.Assuming that the jobs have different basic processing times and the same deterioration rate,jobs can be rejected by paying penalties.The machine is unavailable in a given time interval and the jobs are non-resumable.The objective is to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs.For this NP-hard problem,we design a pseudo-polynomial-time dynamic programming and a fully polynomial-time approximation scheme.3.When the machines may be unavailable in a specified time intervals and jobs are non-resumable,we consider single machine scheduling problem with De Jong’s learning effect and rejection.The objective is to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected job.The actual processing time of the job is related to the position,jobs can be rejected by paying penalties.For this NP-hard problem,an FPTAS is constructed by using procedure partition,and the complexity of the algorithm is analyzed.