The Study Of Some Scheduling Problems With Learning Effects

As a sort of problen widely applied in fields like management science,computer science and control science,the scheduling problem has received extensive attention in recent years.Based on the position-dependent learning effect,three NP-hard scheduling problems are considered in this paper.The three problems are minimizing makespan on two parallel machines,minimizing the total weighted completion time on single machine and minimizing the maximum lateness on single machine.In the second chapter,the problem of minimizing makespan on two parallel machines is studied.First,we establish the integer programming model to find the optimal solution.Then,based on the simulated annealing algorithm,we propose an approximation algorithm SA and prove that the algorithm SA converges to global optimal solution with probability 1.Finally,we analyze the performance of the algorithm SA by numerical simulation.The results of numerical simulation show that the algorithm SA can reach 99%of the optimal value and it is an effective algorithm for the problem.In the third chapter,we discuss two problems on single machine environment,where the objectives are to minimize the total weighted completion time and the maximum lateness.For the problem of minimizing the total weighted completion time,three special cases are discussed,where P_j = P,W_j = w and w_j=kP_j.The optimal schedule for the three special cases are proved in this chapter.For the problem of minimizing the maximum lateness,the three special cases discussed are P_j = P,d_j = d and d_j = kP_j.The optimal schedule for the three special cases are proved in this chapter as well.