Study On Modern Scheduling Problems With Deteiroration And Learning Effects Considerations

Scheduling problem is a kind of important combinatorial optimization problems an d it is an important branch of operational research. The job of processing time in the classical scheduling problems is generally constant. Due to the influence of some pra ctical factors, the job of actual processing time is variable. There are many factors su ch as their position, their starting time and so on. So, the modern scheduling problem s with learning effect and deteriorating effect was proposed. In the influence of many factors, these questions is more complicated than classical scheduling problems, most of them belong to NP-hard problem. With regard to NP-hard problem, in this paper, s ome effective algorithms were proposed on some special cases and their worst case b ound is put forward. Some modern scheduling problems with learning effect and deter iorating effect exists polynomial algorithm. Discussing this kind of problem is also ver y valuable. If the problem exists polynomial algorithm, they can not only solve the cl ass of the problem, also provide similar NP-hard problem with approximate algorith m. For modern scheduling problems with learning effect and deteriorating effect, this paper made a few of the following work:1Modern scheduling problems with learning effects considerations(1) Learning effect of a job depends on its position in a processing sequence. Th e objectives are to minimize the weighted sum of completion times, to minimize the maximum lateness and to minimize the number of tardy jobs. For some special cases, we prove that the weighted shortest processing time (WSPT) rule, the earliest due dat e (EDD) rule and Moore’s algorithm can construct an optimal sequence for these obje ctive functions, respectively. For the general cases, we also give the worst-case bound of these three rules.(2) Single machine scheduling problem with learning effect where the actual proc essing times of jobs are defined by decreasing function of their position in the sequen ce. The due dates of jobs are equal to their actual processing times plus the common slack time. The objective is to determine the optimal schedule and the common slack time simultaneously to minimize the sum of earliness, tardiness and common slack ti me. The problem can be solved in polynomial time and we also provide a polynomial time algorithm to solve the problem.(3) Single machine scheduling problems with the more general sum of the normal processing time based learning effect is considered. If0<α<1, single machine make span minimization problem remain polynomially solvable. We also show that an optim al schedule of the total completion time minimization problem is V-shaped with respe ct to job normal processing times.(4) Single-machine scheduling problems with sum of the normal processing time and the group technology (GT) assumption. The objective of scheduling problem is to minimize the makespan. We show that these problems remain solvable in polynomial time.2Modern scheduling problems with deterioration(1) By time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. We show that, even with the introduction of time-dependent deter ioration to job processing times, the single-machine makespan minimization problem re mains polynomially solvable. We also show that an optimal schedule of the total com pletion time minimization problem is V-shaped with respect to normal job processing t imes(2) We consider a single machine scheduling problem with deteriorating jobs and group technology assumption. The objective of the scheduling problem is to minimize the makespan. We show that the problem remains solvable in polynomial time when general linear deterioration and group technology are considered simultaneously.(3) We studied the m identical parallel-machine and unrelated parallel-machine sc heduling with a deteriorating maintenance activity to minimize the total completion tim e. We showed that each problem can be solved in O(nm+3) time, where n is the nu mber of jobs. 3Modern scheduling problems with deterioration and learning effects consideratio ns(1) We consider two single-machine scheduling problems with the effect of deteri oration and learning. In this model, the processing times of jobs are defined as functi ons of their starting times and positions in a sequence. For the following two objectiv e functions, the weighted sum of completion times and the maximum lateness, this pa per gives two heuristics according to the corresponding problems without learning effe ct. This paper also gives the worst case error bound for the heuristics and provides c omputational results to evaluate the performance of the heuristics.(2) This paper studies two single-machine scheduling problems with the effect of deterioration and learning. For the following two objective functions:the weighted su m of completion times and the maximum lateness, this paper proposes two heuristics according to the corresponding single machine problems without learning effect. This paper also gives the worst-case error bound for the heuristics and provides computatio nal results to evaluate the performance of the heuristics.(3) By the effects of sum of processing time based learning and deterioration, we mean that the processing time of a job is defined by function of its starting time an d total normal processing time of jobs in front of it in the sequence. It is shown that, even with the introduction of the effects of sum of processing time based learning a nd deterioration to job processing times, the single-machine makespan minimization pr oblem remains polynomially solvable.