Parallel-machine Scheduling Of Deteriorating Jobs With Potential Machine Disruptions

In many classical scheduling problems, it assumes that the processing times of jobs are constant and the machines can operated continuously during processing. However, in practice, the machine efficiency deteriorates over time due to machine usage and aging, which will accordingly increase the actual processing times of jobs. This phenomenon is known as deteriorating effect. Moreover, disruption often occurs as a result of some internal or external factors that make machine can't work continuously. Therefore, performing machine maintenance is necessary to improve production efficiency or prevent the failure or breakdown of the machines.This paper considers parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. By deteriorating jobs, it means that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. In addition, some of the machines may become unavailable due to potential machine disruptions, each of which will last for a period of time with a certain probability. Two cases are involved, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance, in which performing machine maintenance will improve the efficiency of the machine by making it return to its original state of efficiency, i.e. the actual processing time of a job will be the same as its normal processing time if it is the first job that starts processing on a disrupted machine after maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. The main contributions of the dissertation are summarized as follows.(1) For the non-resumable case, this paper proves that it is NP-hard in the strong sense when the number of machines is considered to be part of the input and is NP-hard when the number of machines is fixed. For each of performing or not performing machine maintenance cases, this paper develops a pseudo-polynomial time dynamic programming algorithms, establishing that it is NP-hard in the ordinary sense, and proves that the problem when the anticipated disruption occurs on only one of the machines admits a fully polynomial-time approximation scheme when the number of machines is fixed.(2) For the resumable case, this paper proves that it is NP-hard in the strong sense when the number of machines is considered to be part of the input and is NP-hard when the number of machines is fixed and the anticipated disruption occurs on at least two of the machines. For each of performing or not performing machine maintenance cases, this paper develops a pseudo-polynomial time dynamic programming algorithms, establishing that it is NP-hard in the ordinary sense when the number of machines is fixed and the anticipated disruption occurs on at least two of the machines. However, the question as to whether or not the problem when the number of machines is fixed and the anticipated disruption occurs on only one of the machines is NP-hard remains open.