Scheduling Problems With Learning And Deterioration Effect

In order to save processing costs not all the jobs have to be processed in the industrial production process. Some jobs can be rejected. For example, the jobs which need a long processing time. The industry can pay to process outside or purchase. The jobs can be rejected but have to pay the extra fees, which is the so-called rejection penalty. At the same time, due to wearing down and breaking down of the machine, it is demanded to maintain to improve the speed of the processing time in a certain time. In many realistic problems, the jobs require preheat or install the necessary jigs and fixtures before processing and the jobs need to cool down after processing, such as in the industrial processes of steel and metallurgy. During the process of production, the times always contain the setup time and delivery time. The setup time and delivery time of the job affect adversely to its total completion time. Therefore, it is necessary for us to consider the time spent on setup and delivery of the job. This thesis considers the scheduling problems with learning effect, deterioration effect, setup time, delivery time and rejection penalty. The objectives are to minimize the makespan, the total completion time and so on. According to the different conditions of the processing time, the thesis analyzes the complexity of the algorithms for these problems respectively, which shows the problems are solvable in polynomial time. The specific contents are summarized as follows:1) When the job’s processing time is pij=aij+bitij, this thesis considers the unrelated parallel machine scheduling with deteriorating jobs and rejection. The objectives are to minimize the sum of the scheduling criterion of the accepted jobs and the total penalty of the rejected jobs. The scheduling criterions are the total load and the total completion time respectively. The purpose is to find the set of rejected jobs, the non-rejected jobs, and arrange the non-rejected jobs sequence to minimize the objective costs. The objective function of two problems can be transformed into the assignment problem, which shows that the problems are solvable in polynomial time.2) When the job’s processing time is pj[r]= Pjg(r), this thesis considers the single machine scheduling problems with learning effect, setup time and delivery time. The setup time and delivery time depend on a general function of the processing times of the jobs already processed and its scheduled position, for instance, the setup time and delivery time are past-sequence-dependent (p-s-d). The objectives are to minimize the makespan, the total completion time, the total weighted completion time, the total tardiness, the maximum tardiness and the maximum lateness. We provide the optimal schedules for some single-machine problems and show that they are solvable in polynomial time.3) This thesis considers the single machine scheduling problems with learning and deterioration effect, maintenance activities and rejection. The objectives are to minimize the sum of the scheduling criterion of the accepted jobs and the total penalty of the rejected jobs. The scheduling criterions are the makespan and the total completion time respectively. This thesis considers the job’s processing time arepjr= (Pj+bt)rα and pjr= (Pj-bt)rα, respectively, which shows that the two problems are solvable in polynomial time.