Some Tardiness Problems With Machine Disruption

The paper mainly studies two machine-scheduling problems under disruption. This problem can be described as:the jobs have been assigned to two identical parallel machines. For some reason ,one of the machines may disrupt at a particular time and if it happens the machine will become unavailable for certain duration. Which makes jobs assigned to the disrupted machine can not be timely processing, and thus these parts can either be processed by the same machine after disruption or can be transferred to another available machine for processing, When the two machines after processing, arranged in the normal operation of the machine processing of the jobs can also be transferred to the machine after the restoration process,(1) We study how to organize a new processing sequence, making the objective function of the sum of unit penalties (?)is minimized; (2) The n jobs have been assigned to two identical parallel machines, the article studies how to re-arrange the order of jobs, and how to assign due dates to each job, making the objective function(?),(?)is minimized. Full-text is divided into four chapters.Chapter 1 is the introduction, focuses on combinatorial optimization, computational complexity, and presents the background of the problem and research methods of scheduling.Chapter 2 discusses problem (1). If transfer time T = 0 an optimal algorithm of this problem is proposed, When the job transfer time T > 0, the problem is NP hard problem, An approximation algorithm is proposed in this paper and it's difference bound is 1,the paper proves it, the time complexity of the algorithm is O(nlogn ).Chapter 3 discusses problem (2). Studies due dates can be assignable to jobs ,In which there is a disruption happen to one of the two parallel machine, and extended to the case of m parallel machines, When the due dates(?)assigned to the processing jobs, consider the objective function(?),(?), the article gives an optimal scheduling. For the above given order, when the due dates d_[1], d_[2],……d_[n] of the allocation according to EDD order for processing jobs, the objective function of these are proved to be optimal.Chapter 4 summarizes the paper and proposes the prospects.