Scheduling Problem With Non-availability Interval And Rejection

The actual processing time of a job is longer if it is processed later in a sequence in many realistic problems. Examples can be found in financial management, steel production, fire fighting, resource allocation and national defense,etc., in which any delay in processing a job may result in deterioration in accomplishing the job. At the same time, the machine may be unavailable because of periodical repairs preventive and maintenances, namely, non-availability interval. In many manufacturing environments, however, a job need to be preprocessed before it undergoes processing. This preprocessing time can be considered as job release time.At the same time, machines are not available at all times because of periodical repairs preventive and maintenances during the scheduling period, namely,non-availability interval. It is always assumed in traditional research that all the jobs have to be processed. In the setting of scheduling with rejection, the manager may decide not to process some jobs if they are not profitable. While saving some direct production cost, a rejected job incurs some penalty due to the rejection, namely,rejection penalty. Examples can be found in many industries such as aircraft,electronics, etc.This paper studied the scheduling problems with release time, deteriorating effect,rejection and a non-availability interval. In this model, release dates of all the jobs are equal. Job processing times are not fixed because jobs may deteriorate while waiting to be processed. A job is either rejected, in which case a rejection penalty has to be paid or processed on the machine. The machine can’t process any job in the non-availability interval. The specific content is summarized as follows:1. We study the single machine scheduling problem that the objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of all the rejected jobs. First we propose a pseudo-polynomial time dynamic programming algorithm. And then, we design a fully polynomial-time approximation scheme to solve the problem, and analyze the time complexity.2. We study the single machine scheduling problem that the objective is to minimize the total weighted completion time of the accepted jobs plus the total penalty of the rejected jobs. First, we indicate the problem is NP-hard in the ordinary sense. And then, a fully polynomial-time approximation scheme is given for theproblem, and the time complexity is analyzed for the fully polynomial-time approximation scheme.3. We study the two-machine flowshop scheduling problem with an availability constraint on one machine and the objective is to minimize the total weighted completion time of the accepted jobs plus the total penalty of the rejected jobs. First,we indicate the problem is NP-hard in the ordinary sense. And then, a fully polynomial-time approximation scheme is given for the problem, and the time complexity is analyzed for the fully polynomial-time approximation scheme.